Extensive phylogenetic analyses of the updated sequence data of mammalian mitochondrial genomes were carried out using the maximum likelihood method in order to resolve deep branchings in eutherian evolution. The divergence times in the mammalian tree were estimated by a relaxed molecular clock of the mitochondrial proteins calibrated with multiple references. A Chiroptera/Eulipotyphla (i.e. bat/mole) clade and a close relationship of this clade to Fereuungulata (Carnivora+Perissodactyla+Cetartiodactyla) were reconfirmed with high statistical significance. However, a support for a monophyly of Fereuungulata relative to the Chiroptera/Eulipotyphla clade was fragile, and we suggest that the three branchings among Carnivora, Perissodactyla, Cetartiodactyla and Chiroptera/Eulipotyphla occurred successively in a short time period, estimated to be approximately 77Myr BP. The Chiroptera/Eulipotyphla divergence was estimated to roughly coincide with the Cretaceous-Tertiary boundary (65Myr BP). The monophyly of Rodentia, the Lagomorpha/Rodentia clade (traditionally called Glires), and the Afrotheria/Xenarthra clade were preferred over alternative relationships, but the supports of these clades were not strong enough to exclude other possibilities. Although several super-order taxa of eutherians were strongly supported by the analyses of the mitochondrial genome data, the branching order in the deepest part of the eutherian tree remained ambiguous from the data presently available.