Here we report DNA sequences from mitochondrial cytochrome b gene segments (1,005 base pairs per species) for the extinct woolly mammoth (Mammuthus primigenius) and Steller's sea cow (Hydrodamalis gigas) and the extant Asian elephant (Elephas maximus), the Western Indian manatee (Trichechus manatus), and the hyrax (Procavia capensis). These molecular data have allowed us to construct the phylogeny for the Tethytheria. Our molecular data resolve the trichotomy between the two species of living elephants and the mammoth and confirm that the mammoth was more closely related to the Asian elephant than to the African elephant. Our data also suggest that the sea cow–dugong divergence was likely as ancient as the dugong–manatee split, and it appears to have been much earlier (22 million years ago) than had been previously estimated (4–8 million years ago) by immunological comparison.