BACKGROUND: The phylogeny of Cetacea (whales) is not fully resolved with substantial support. The ambiguous and conflicting results of multiple phylogenetic studies may be the result of the use of too little data, phylogenetic methods that do not adequately capture the complex nature of DNA evolution, or both. In addition, there is also evidence that the generic taxonomy of Delphinidae (dolphins) underestimates its diversity. To remedy these problems, we sequenced the complete mitochondrial genomes of seven dolphins and analyzed these data with partitioned Bayesian analyses. Moreover, we incorporate a newly-developed "relaxed" molecular clock to model heterogenous rates of evolution among cetacean lineages. RESULTS: The "deep" phylogenetic relationships are well supported including the monophyly of Cetacea and Odontoceti. However, there is ambiguity in the phylogenetic affinities of two of the river dolphin clades Platanistidae (Indian River dolphins) and Lipotidae (Yangtze River dolphins). The phylogenetic analyses support a sister relationship between Delphinidae and Monodontidae + Phocoenidae. Additionally, there is statistically significant support for the paraphyly of Tursiops (bottlenose dolphins) and Stenella (spotted dolphins). CONCLUSION: Our phylogenetic analysis of complete mitochondrial genomes using recently developed models of rate autocorrelation resolved the phylogenetic relationships of the major Cetacean lineages with a high degree of confidence. Our results indicate that a rapid radiation of lineages explains the lack of support the placement of Platanistidae and Lipotidae. Moreover, our estimation of molecular divergence dates indicates that these radiations occurred in the Middle to Late Oligocene and Middle Miocene, respectively. Furthermore, by collecting and analyzing seven new mitochondrial genomes, we provide strong evidence that the delphinid genera Tursiops and Stenella are not monophyletic, and the current taxonomy masks potentially interesting patterns of morphological, physiological, behavioral, and ecological evolution.