Local circuits in the spinal cord that generate locomotion are termed central pattern generators (CPGs). These provide coordinated bilateral control over the normal limb alternation that underlies walking. The molecules that organize the mammalian CPG are unknown. Isolated spinal cords from mice lacking either the EphA4 receptor or its ligand ephrinB3 have lost left-right limb alternation and instead exhibit synchrony. We identified EphA4-positive neurons as an excitatory component of the locomotor CPG. Our study shows that dramatic locomotor changes can occur as a consequence of local genetic rewiring and identifies genes required for the development of normal locomotor behavior.