The diversity of body plans of mammals accelerates the innovation of lifestyles and the extensive adaptation to different habitats, including terrestrial, aerial and aquatic habitats. However, the genetic basis of those phenotypic modifications, which have occurred during mammalian evolution, remains poorly explored. In the present study, we synthetically surveyed the evolutionary pattern of Hox clusters that played a powerful role in the morphogenesis along the head-tail axis of animal embryos and the main regulatory factors (Mll, Bmi1 and E2f6) that control the expression of Hox genes. A deflected density of repetitive elements and lineage-specific radical mutations of Mll have been determined in marine mammals with morphological changes, suggesting that evolutionary changes may alter Hox gene expression in these lineages, leading to the morphological modification of these lineages. Although no positive selection was detected at certain ancestor nodes of lineages, the increased ω values of Hox genes implied the relaxation of functional constraints of these genes during the mammalian evolutionary process. More importantly, 49 positively-selected sites were identified in mammalian lineages with phenotypic modifications, indicating adaptive evolution acting on Hox genes and regulatory factors. In addition, 3 parallel amino acid substitutions in some Hox genes were examined in marine mammals, which might be responsible for their streamlined body.