Background Integration of diverse data (molecules, fossils) provides the most robust test of the phylogeny of cetaceans. Positioning key fossils is critical for reconstructing the character change from life on land to life in the water. Methodology/Principal Findings We reexamine relationships of critical extinct taxa that impact our understanding of the origin of Cetacea. We do this in the context of the largest total evidence analysis of morphological and molecular information for Artiodactyla (661 phenotypic characters and 46,587 molecular characters, coded for 33 extant and 48 extinct taxa). We score morphological data for Carnivoramorpha, †Creodonta, Lipotyphla, and the †raoellid artiodactylan †Indohyus and concentrate on determining which fossils are positioned along stem lineages to major artiodactylan crown clades. Shortest trees place Cetacea within Artiodactyla and close to †Indohyus, with †Mesonychia outside of Artiodactyla. The relationships of †Mesonychia and †Indohyus are highly unstable, however - in trees only two steps longer than minimum length, †Mesonychia falls inside Artiodactyla and displaces †Indohyus from a position close to Cetacea. Trees based only on data that fossilize continue to show the classic arrangement of relationships within Artiodactyla with Cetacea grouping outside the clade, a signal incongruent with the molecular data that dominate the total evidence result. Conclusions/Significance Integration of new fossil material of †Indohyus impacts placement of another extinct clade †Mesonychia, pushing it much farther down the tree. The phylogenetic position of †Indohyus suggests that the cetacean stem lineage included herbivorous and carnivorous aquatic species. We also conclude that extinct members of Cetancodonta (whales + hippopotamids) shared a derived ability to hear underwater sounds, even though several cetancodontans lack a pachyostotic auditory bulla. We revise the taxonomy of living and extinct artiodactylans and propose explicit node and stem-based definitions for the ingroup.
