To obtain a more complete understanding of the evolutionary history of the leaf-eating monkeys we have examined the mitochondrial genome sequence of two African and six Asian colobines. Although taxonomists have proposed grouping the "odd-nosed" colobines (proboscis monkey, douc langur, and the snub-nosed monkey) together, phylogenetic support for such a clade has not been tested using molecular data. Phylogenetic analyses using parsimony, maximum likelihood, and Bayesian methods support a monophyletic clade of odd-nosed colobines consisting of Nasalis, Pygathrix, and Rhinopithecus, with tentative support for Nasalis occupying a basal position within this clade. The African and Asian colobine lineages are inferred to have diverged by 10.8 million years ago (mya or Ma). Within the Asian colobines the odd-nosed clade began to diversify by 6.7 Ma. These results augment our understanding of colobine evolution, particularly the nature and timing of the colobine expansion into Asia. This phylogenetic information will aid those developing conservation strategies for these highly endangered, diverse, and unique primates.