Abstract Background Many electron transport chain (ETC) genes show accelerated rates of nonsynonymous nucleotide substitutions in anthropoid primate lineages, yet in non-anthropoid lineages the ETC proteins are typically highly conserved. Here, we test the hypothesis that COX5A, the ETC gene that encodes cytochrome c oxidase subunit 5A, shows a pattern of anthropoid-specific adaptive evolution, and investigate the distribution of this protein in catarrhine brains. Results In a dataset comprising 29 vertebrate taxa, including representatives from all major groups of primates, there is nearly 100% conservation of the COX5A amino acid sequence among extant, non-anthropoid placental mammals. The most recent common ancestor of these species lived about 100 million years (MY) ago. In contrast, anthropoid primates show markedly elevated rates of nonsynonymous evolution. In particular, branch site tests identify five positively selected codons in anthropoids, and ancestral reconstructions infer that substitutions in these codons occurred predominantly on stem lineages (anthropoid, ape and New World monkey) and on the human terminal branch. Examination of catarrhine brain samples by immunohistochemistry characterizes for the first time COX5A protein distribution in the primate neocortex, and suggests that the protein is most abundant in the mitochondria of large-size projection neurons. Real time quantitative PCR supports previous microarray results showing COX5A is expressed in cerebral cortical tissue at a higher level in human than in chimpanzee or gorilla. Conclusion Taken together, these results suggest that both protein structural and gene regulatory changes contributed to COX5A evolution during humankind's ancestry. Furthermore, these findings are consistent with the hypothesis that adaptations in ETC genes contributed to the emergence of the energetically expensive anthropoid neocortex.