In animals, interactions among gene products of mitochondrial and nuclear genomes (mitonuclear interactions) are of profound fitness, evolutionary, and ecological significance. Most fundamentally, the oxidative phosphorylation (OXPHOS) complexes responsible for cellular bioenergetics are formed by the direct interactions of 13 mitochondrial-encoded and ∼80 nuclear-encoded protein subunits in most animals. It is expected that organisms will develop genomic architecture that facilitates co-adaptation of these mitonuclear interactions and enhances biochemical efficiency of OXPHOS complexes. In this perspective, we present principles and approaches to understanding the co-evolution of these interactions, with a novel focus on how genomic architecture might facilitate it. We advocate that recent interdisciplinary advances assist in the consolidation of links between genotype and phenotype. For example, advances in genomics allow us to unravel signatures of selection in mitochondrial and nuclear OXPHOS genes at population-relevant scales, while newly published complete atomic-resolution structures of the OXPHOS machinery enable more robust predictions of how these genes interact epistatically and co-evolutionarily. We use three case studies to show how integrative approaches have improved the understanding of mitonuclear interactions in OXPHOS, namely those driving high-altitude adaptation in bar-headed geese, allopatric population divergence in Tigriopus californicus copepods, and the genome architecture of nuclear genes coding for mitochondrial functions in the eastern yellow robin.