Mammalian oxidative phosphorylation (OXPHOS) complexes I, III, IV and V are assembled from both mitochondrial DNA (mtDNA) and nuclear DNA (nDNA) encoded subunits, with complex I encompassing 39 nDNA and seven mtDNA subunits. Yet the sequence variation of the mtDNA genes is more than ten fold greater than that of the nDNA encoded genes of the OXPHOS complexes and the mtDNA proteins have been found to be influenced by positive (adaptive) selection. To maintain a functional complex I, nDNA and mtDNA subunits must interact, implying that certain nDNA complex I genes may also have been influenced by positive selection. To determine if positive selection has influenced nDNA complex I genes, we analyzed the DNA sequences of all of the nDNA and mtDNA encoded complex I subunits from orangutan, gorilla, chimpanzee, human and all available vertebrate sequences. This revealed that three nDNA complex I genes (NDUFC2, NDUFA1, and NDUFA4) had significantly increased amino acid substitution rates by both PAML and Z-test, suggesting that they have been subjected to adaptive selection during primate radiation. Since all three of these subunits reside in the membrane domain of complex I along with the mtDNA subunits, we compared amino acid changes in these three nDNA genes with those of the mtDNA genes across species. Changes in the nDNA NDUFC2 cysteine 39 were found to correlate with those in the mtDNA ND5 cysteine 330. Therefore, adaptive selection has influenced some nDNA complex I genes and nDNA and mtDNA complex I genes may have co-evolved.