The evolution of morphological characters is mediated by the evolution of developmental genes. Evolutionary changes can either affect cis-regulatory elements, leading to differences in their temporal and spatial regulation, or affect the coding region. Although there is ample evidence for the importance of cis-regulatory evolution, it has only recently been shown that transcription factors do not remain functionally equivalent during evolution. These results suggest that the evolution of transcription factors may play an active role in the evolution of development. To test this idea we investigated the molecular evolution of two genes essential for the development and function of the mammalian female reproductive organs, HoxA-11 and HoxA-13. We predicted that if coding-region evolution plays an active role in developmental evolution, then these genes should have experienced adaptive evolution at the origin of the mammalian female reproductive system. We report the sequences of HoxA-11 from basal mammalian and amniote taxa and analyse HoxA-11 and HoxA-13 for signatures of adaptive molecular evolution. The data demonstrate that these genes were under strong positive (directional) selection in the stem lineage of therian and eutherian mammals, coincident with the evolution of the uterus and vagina. These results support the idea that adaptive evolution of transcription factors can be an integral part in the evolution of novel structures.