Abstract The phylogenetic relationships among the genera of the tribe Papionini are inferred using a taxonomic congruence approach in which gene trees derived for eight unlinked genetic sequence datasets are compared. Population genetics theory predicts that species relationships will be revealed with greater probability when the topology of gene trees from many unlinked loci are found to be congruent. The theory underlying this approach is described. Monophyly of the mangabeys is not supported by any of the gene trees; instead, they are polyphyletic with Cercocebus found to be the sister taxon to Mandrillus in five gene trees (with no conflicting trees), and Lophocebus found to be closely related to Papio and/or Theropithecus in all trees. Theropithecus and Papio are not strongly supported as sister taxa (present in one or two trees only); Lophocebus and Papio are supported as sister taxa in the majority of trees. A close relationship between Mandrillus and Papio is not supported in any of the trees. The relationships among Papio, Lophocebus, and Theropithecus cannot be resolved by congruence, probably due to the short time interval estimated between their divergences. The mtDNA COII sequences are used to estimate divergence dates within the papionins. The internode between the divergences of these species is estimated to be between 290 ka and 370 ka. Lastly, the evolution of morphological features such as long faces, suborbital facial fossae, and terrestrial skeletal adaptations is discussed.