The homeobox (Hox) genes Hoxd12 and Hoxd13 control digit patterning and limb formation in tetrapods. Both show strong expression in the limb bud during embryonic development, are highly conserved across vertebrates, and show mutations that are associated with carpal, metacarpal, and phalangeal deformities. The most dramatic evolutionary reorganization of the mammalian limb has occurred in cetaceans (whales, dolphins, and porpoises), in which the hind limbs have been lost and the forelimbs have evolved into paddle-shaped flippers. We reconstructed the phylogeny of digit patterning in mammals and inferred that digit number has changed twice in the evolution of the cetacean forelimb. First, the divergence of the early cetaceans from their even-toed relatives coincided with the reacquisition of the pentadactyl forelimb, whereas the ancestors of tetradactyl baleen whales (Mysticeti) later lost a digit again. To test whether the evolution of the cetacean forelimb is associated with positive selection or relaxation of Hoxd12 and Hoxd13, we sequenced these genes in a wide range of mammals. In Hoxd12, we found evidence of Darwinian selection associated with both episodes of cetacean forelimb reorganization. In Hoxd13, we found a novel expansion of a polyalanine tract in cetaceans compared with other mammals (17/18 residues vs. 14/15 residues, respectively), lengthening of which has previously been shown to be linked to synpolydactyly in humans and mice. Both genes also show much greater sequence variation among cetaceans than across other mammalian lineages. Our results strongly implicate 5′HoxD genes in the modulation of digit number, web forming, and the high morphological diversity of the cetacean manus.