The order Cetartiodactyla includes cetaceans (whales, dolphins and porpoises) that are found in all oceans and seas, as well as in some rivers, and artiodactyls (ruminants, pigs, peccaries, hippos, camels and llamas) that are present on all continents, except Antarctica and until recent invasions, Australia. There are currently 332 recognized cetartiodactyl species, which are classified into 132 genera and 22 families. Most phylogenetic studies have focused on deep relationships, and no comprehensive time-calibrated tree for the group has been published yet. In this study, 128 new complete mitochondrial genomes of Cetartiodactyla were sequenced and aligned with those extracted from nucleotide databases. Our alignment includes 14,902 unambiguously aligned nucleotide characters for 210 taxa, representing 183 species, 107 genera, and all cetartiodactyl families. Our mtDNA data produced a statistically robust tree, which is largely consistent with previous classifications. However, a few taxa were found to be para- or polyphyletic, including the family Balaenopteridae, as well as several genera and species. Accordingly, we propose several taxonomic changes in order to render the classification compatible with our molecular phylogeny. In some cases, the results can be interpreted as possible taxonomic misidentification or evidence for mtDNA introgression. The existence of three new cryptic species of Ruminantia should therefore be confirmed by further analyses using nuclear data. We estimate divergence times using Bayesian relaxed molecular clock models. The deepest nodes appeared very sensitive to prior assumptions leading to unreliable estimates, primarily because of the misleading effects of rate heterogeneity, saturation and divergent outgroups. In addition, we detected that Whippomorpha contains slow-evolving taxa, such as large whales and hippos, as well as fast-evolving taxa, such as river dolphins. Our results nevertheless indicate that the evolutionary history of cetartiodactyls was punctuated by four main phases of rapid radiation during the Cenozoic era: the sudden occurrence of the three extant lineages within Cetartiodactyla (Cetruminantia, Suina and Tylopoda); the basal diversification of Cetacea during the Early Oligocene; and two radiations that involve Cetacea and Pecora, one at the Oligocene/Miocene boundary and the other in the Middle Miocene. In addition, we show that the high species diversity now observed in the families Bovidae and Cervidae accumulated mainly during the Late Miocene and Plio-Pleistocene.