This article presents the first results of a project in underwater modular robotics, called Neubots. The goals of the projects are to explore, following Von Neumann’s ideas, potential mechanisms underlying self-organization and self-replication. We briefly explain the design features of the module units. We then present simulation results of the artificial co-evolution of body structures and neural controllers for locomotion. The neural controllers are inspired from the central pattern generators underlying locomotion in vertebrate animals. They are composed of multiple neural oscillators which are connected together by a specific type of coupling called synaptic spreading. The co-evolution of body and controller leads to interesting robots capable of efficient swimming. Interesting features of the neural controllers include the possibility to modulate the speed of locomotion by varying simple input signals, the robustness against perturbations, and the distributed nature of the controllers which makes them well suited for modular robotics.