Metabolic processes in eukaryotic cells depend on interactions between mitochondrial and nuclear gene products (mitonuclear interactions). These interactions could have a direct role in population divergence. Here, we study mitonuclear co-evolution in a widespread bird that experienced population divergence followed by bidirectional mitochondrial introgression into different nuclear backgrounds. Using >60,000 single nucleotide polymorphisms, we quantify patterns of nuclear genetic differentiation between populations that occupy areas with different climates and harbour deeply divergent mitochondrial lineages despite ongoing nuclear gene flow. We find that strong genetic differentiation and sequence divergence in a region of ~15.4 megabases on chromosome 1A mirror the geographic pattern of mitochondrial DNA divergence. This result is seen in two different transects representing populations with different nuclear backgrounds. The chromosome 1A region is enriched for genes performing mitochondrial functions (N-mt genes). Molecular signatures of selective sweeps in this region alongside those in the mitochondrial genome suggest a history of adaptive mitonuclear co-introgression. Moreover, evidence for large linkage disequilibrium blocks in this genomic region suggests that low recombination could facilitate functional interactions between co-evolved nuclear alleles. Our results are consistent with mitonuclear co-evolution as an important mechanism for population divergence and local adaptation.