The African and Asian elephants and the mammoth diverged ca. 4-6 million years ago and their phylogenetic relationship has been controversial. Morphological studies have suggested a mammoth Asian elephant relationship, while molecular studies have produced conflicting results. We obtained cytochrome b sequences of up to 545 base pairs from five mammoths, 14 Asian and eight African elephants. A high degree of polymorphism is detected within species. With a dugong sequence used as the outgroup, parsimony and maximum-likelihood analyses support a mammoth African elephant clade. As the dugong is a very distant outgroup, we employ likelihood analysis to root the tree with a molecular clock, and use bootstrap and Bayesian analyses to quantify the relative support for different topologies. The analyses support the mammoth African elephant relationship, although other trees cannot be rejected. Ancestral polymorphisms may have resulted in gene trees differing from the species phylogeny Examination of morphological data, especially from primitive fossil members, indicates that some supposed synapomorphies between the mammoth and Asian elephant are variable, others convergent or autapomorphous. A mammoth African elephant relationship is not excluded. Our results highlight the need, in both morphological and molecular phylogenetics, for multiple markers and close attention to within-taxon variation and outgroup selection.