Background: The evolutionary history of the Old World monkey tribe Papionini comprising the genera Macaca, Mandrillus, Cercocebus, Lophocebus, Theropithecus, Rungwecebus and Papio is still matter of debate. Although the African Papionini (subtribe Papionina) are generally considered to be the sister lineage to the Asian Papionini (subtribe Macacina), previous studies based on morphological data, nuclear or mitochondrial sequences have shown contradictory phylogenetic relationships among and within both subtribes. To further elucidate the phylogenetic relationships among papionins and to estimate divergence ages we generated mitochondrial genome data and combined them with previously published sequences. Results: Our mitochondrial gene tree comprises 33 papionins representing all genera of the tribe except Rungwecebus. In contrast to most previous studies, the obtained phylogeny suggests a division of the Papionini into three main mitochondrial clades with similar ages: 1) Papio, Theropithecus, Lophocebus; 2) Mandrillus, Cercocebus; and 3) Macaca; the Mandrillus + Cercocebus clade appears to be more closely related to Macaca than to the other African Papionini. Further, we find paraphyletic relationships within the Mandrillus + Cercocebus clade as well as in Papio. Relationships among Theropithecus, Lophocebus and Papio remain unresolved. Divergence ages reveal initial splits within the three mitochondrial clades around the Miocene/Pliocene boundary and differentiation of Macaca species groups occurred on a similar time scale as those found between genera of the subtribe Papionina. Conclusion: Due to the largely well-resolved mitochondrial phylogeny, our study provides new insights into the evolutionary history of the Papionini. Results show some contradictory relationships in comparison to previous analyses, notably the paraphyly within the Cercocebus + Mandrillus clade and three instead of only two major mitochondrial clades. Divergence ages among species groups of macaques are similar to those among African Papionini genera, suggesting that diversification of the mitochondrial genome is of a similar magnitude in both subtribes. However, since our mitochondrial tree represents just a single gene tree that most likely does not reflect the true species tree, extensive nuclear sequence data is required to illuminate the true species phylogeny of papionins and to trace possible ancient hybridization events among lineages.