In most animals, mitochondrial genomes (mtDNA) evolve at a higher rate than nuclear genomes (nDNA), which sets the stage for incompatibilities between the products of the two genomes. Mitochondrial and nuclear -encoded proteins are integrated in aerobic respiration which often requires their co-functionality. These requisite mitonuclear interactions are the basis for the mitonuclear coevolution hypothesis which posits that rapid mt evolution drives compensatory nuclear evolution in genes that encode mt-interacting proteins. Although mt evolution rates vary across taxa, one signature of coevolution is coordinated variation in mitochondrial and mitochondrial-targeted nuclear-encoded proteins (n-mt) substitution rates. Here, we predicted that n-mt proteins would show correlated evolutionary rates with mt genes but that other n-encoded non mitochondrial-interacting proteins would not. Using sequences from 59 mammal species across eight orders, we found strong correlations between evolutionary rates of mt and n-mt proteins involved in oxidative phosphorylation. In contrast, evolutionary rates of nuclear proteins that do not interact with mt proteins, but also function in energy production, were only weakly correlated with mt substitution rates. In light of other recent studies that show elevated positive selection on n-mt but not other n genes, our results suggest that nuclear compensation is one mechanism by which mammals maintain mitonuclear coevolution.