In this paper we study online gait opti- mization for modular robots. The learning strategy we apply is distributed, independent on robot mor- phology, and easy to implement. First we demonstrate how the strategy allows an ATRON robot to adapt to faults and changes in its morphology and we study the strategy’s scalability. Second we extend the strategy to learn the parameters of gait-tables for ATRON and M-TRAN robots.We conclude that the presented strategy is effective for online learning of gaits for most types of modular robots and that learning can effectively be distributed by having independent pro- cesses learning in parallel.