A fascinating question in biology is how molecular changes in developmental pathways lead to macroevolutionary changes in morphology. Mutations in homeotic (Hox) genes have long been suggested as potential causes of morphological evolution, and there is abundant evidence that some changes in Hox expression patterns correlate with transitions in animal axial pattern. A major morphological transition in metazoans occurred about 400 million years ago, when six-legged insects diverged from crustacean-like arthropod ancestors with multiple limbs. In Drosophila melanogaster and other insects, the Ultrabithorax (Ubx) and abdominal A (AbdA, also abd-A) Hox proteins are expressed largely in the abdominal segments, where they can suppress thoracic leg development during embryogenesis. In a branchiopod crustacean, Ubx/AbdA proteins are expressed in both thorax and abdomen, including the limb primordia, but do not repress limbs. Previous studies led us to propose that gain and loss of transcriptional activation and repression functions in Hox proteins was a plausible mechanism to diversify morphology during animal evolution. Here we show that naturally selected alteration of the Ubx protein is linked to the evolutionary transition to hexapod limb pattern.