Cytochrome c (CYC) oxidase (COX), a multisubunit enzyme that functions in mitochondrial aerobic energy production, catalyzes the transfer of electrons from CYC to oxygen and participates in creating the electrochemical gradient used for ATP synthesis. Modeling three-dimensional structural data on COX and CYC reveals that 57 of the >1,500 COX residues can be implicated in binding CYC. Because of the functional importance of the transfer of electrons to oxygen, it might be expected that natural selection would drastically constrain amino acid replacement rates of CYC and COX. Instead, in anthropoid primates, although not in other mammals, CYC and COX show markedly accelerated amino acid replacement rates, with the COX acceleration being much greater at the positions that bind CYC than at those that do not. Specifically, in the anthropoid lineage descending from the last common ancestor of haplorhines (tarsiers and anthropoids) to that of anthropoids (New World monkeys and catarrhines) and that of catarrhines (Old World monkeys and apes, including humans), a minimum of 27 of the 57 COX amino acid residues that bind CYC were replaced, most frequently from electrostatically charged to noncharged residues. Of the COX charge-bearing residues involved in binding CYC, half (11 of 22) have been replaced with uncharged residues. CYC residues that interact with COX residues also frequently changed, but only two of the CYC changes altered charge. We suggest that reducing the electrostatic interaction between COX and CYC was part of the adaptive evolution underlying the emergence of anthropoid primates.