Addition of the recently discovered fossil Nalacetus to a phylogenetic analysis of basicranial, cranial, dental, postcranial, and soft morphological characters reveals that it is the most basal cetacean, and that mesonychians form the monophyletic sister group to Cetacea. The molars of Nalacetus elucidate transformations in dental morphology that occurred early in the cetacean radiation and clarify certain derived differences in molar cusp position between cetaceans and the extinct clade, Mesonychia, hypothesized to be their sister taxon. Nalacetus and other archaic cetaceans share derived vertically elongate shearing facets on the lower molars. Applying the Extant Phylogenetic Bracket, we advance the hypothesis that these facets are an osteological correlate of aquatic predation. Our functional interpretation of this character and its distribution within Cetacea indicates that a behavioral change in tooth use characterized the origin of the clade. Comparison of the transformation of this dental character with that of the cetacean pelvis indicates that a change in tooth use (feeding behavior) occurred before loss of the ability to engage in terrestrial locomotion. The most parsimonious phylogenetic hypothesis presented here has a significant fit with the stratigraphic record as determined by the Manhattan Stratigraphic Measure, which is corroborated by retention indices of stratigraphic data. Ghost lineages necessitated by the phylogenetic hypothesis extend the stratigraphic range of Cetacea into the middle Paleocene (Torrejonian), ten million years earlier than the oldest cetacean fossil currently known. Primitive features of Nalacetus, the large number of synapomorphies diagnosing Cetacea, and the implied ghost lineage suggest that the early cetacean radiation was much more extensive than has been previously recognized.