The emergence of limb-driven locomotor behaviors was a key event in the evolution of vertebrates and fostered the transition from aquatic to terrestrial life. We show that the generation of limb-projecting lateral motor column (LMC) neurons in mice relies on a transcriptional autoregulatory module initiated via transient activity of multiple genes within the HoxA and HoxC clusters. Repression of this module at thoracic levels restricts expression of LMC determinants, thus dictating LMC position relative to the limbs. This suppression is mediated by a key regulatory domain that is specifically found in the Hoxc9 proteins of appendage-bearing vertebrates. The profile of Hoxc9 expression inversely correlates with LMC position in land vertebrates and likely accounts for the absence of LMC neurons in limbless species such as snakes. Thus, modulation of both Hoxc9 protein function and Hoxc9 gene expression likely contributed to evolutionary transitions between undulatory and ambulatory motor circuit connectivity programs.