Knowledge of the phylogenetic position of the order Cetacea (whales, dolphins, and porpoises) within Mammalia is of central importance to evolutionary biologists studying the transformations of biological form and function that accompanied the shift from fully terrestrial to fully aquatic life in this clade. Phylogenies based on molecular data and those based on morphological data both place cetaceans among ungulates but are incongruent in other respects. Morphologists argue that cetaceans are most closely related to mesonychians, an extinct group of terrestrial ungulates. They have disagreed, however, as to whether Perissodactyla (odd-toed ungulates) or Artiodactyla (even-toed ungulates) is the extant clade most closely related to Cetacea, and have long maintained that each of these orders is monophyletic. The great majority of molecule-based phylogenies show, by contrast, not only that artiodactyls are the closest extant relatives of Cetacea, but also, that Artiodactyla is paraphyletic unless cetaceans are nested within it, often as the sister group of hippopotamids. We tested morphological evidence for several hypotheses concerning the sister taxon relationships of Cetacea in a maximum parsimony analysis of 123 morphological characters from 10 extant and 30 extinct taxa. We advocate treating certain multistate characters as ordered because such a procedure incorporates information about hierarchical morphological transformation. In all most-parsimonious trees, whether multistate characters are ordered or unordered, Artiodactyla is the extant sister taxon of Cetacea. With certain multistate characters ordered, the extinct clade Mesonychia (Mesonychidae + Hapalodectidae) is the sister taxon of Cetacea, and Artiodactyla is monophyletic. When all fossils are removed from the analysis, Artiodactyla is paraphyletic with Cetacea nested inside, indicating that inclusion of mesonychians and other extinct stem taxa in a phylogenetic analysis of the ungulate clade is integral to the recovery of artiodactyl monophyly. Phylogenies derived from molecular data alone may risk recovering inconsistent branches because of an inability to sample extinct clades, which by a conservative estimate amounts to 89% of the ingroup. Addition of data from recently described cetacean astragali attributed to cetaceans does not overturn artiodactyl monophyly.