In this paper we present a novel information-theoretic measure of spatiotemporal coordination in a modular robotic system, and use it as a fitness function in evolving the system. This approach exemplifies a new methodology formalizing co-evolution in multi-agent adaptive systems: information-driven evolutionary design. The methodology attempts to link together different aspects of information transfer involved in adaptive systems, and suggests to approximate direct task-specific fitness functions with intrinsic selection pressures. In particular, the information-theoretic measure of coordination employed in this work estimates the generalized correlation entropy K 2 and the generalized excess entropy E2 computed over a multivariate time series of actuators' states. The simulated modular robotic system evolved according to the new measure exhibits regular locomotion and performs well in challenging terrains.