Nuclear and mitochondrial genomes have to work in concert to generate a functional oxidative phosphorylation (OXPHOS) system. We have previously shown that we could restore partial OXPHOS function when chimpanzee or gorilla mitochondrial DNA (mtDNA) were introduced into human cells lacking mtDNA. However, we were unable to maintain orangutan mitochondrial DNA in a human cell. We have now produced chimpanzee, gorilla, orangutan, and baboon cells lacking mtDNA and attempted to introduce mtDNA from different apes into them. Surprisingly, we were able to maintain human mtDNA in an orangutan nuclear background, even though these cells showed severe OXPHOS abnormalities, including a complete absence of assembled ATP synthetase. Phylogenetic analysis of complex V mtDNA-encoded subunits showed that they are among the most evolutionarily divergent components of the mitochondrial genome between orangutan and the other apes. Our studies showed that adaptive coevolution of nuclear and mitochondrial components in apes can be fast and accelerate in recent branches of anthropoid primates.