Mitochondrial (mtDNA) and nuclear (nDNA) genes interact to govern metabolic pathways of mitochondria. When differentiated populations interbreed at secondary contact, incompatibilities between mtDNA of one population and nDNA of the other could result in low fitness of hybrids. Hermit Warblers (S. occidentalis) and Townsend’s Warblers (Setophaga townsendi) exhibit distinct mtDNA haplotypes and a few nDNA regions of high differentiation, whereas coastal S. townsendi displays a mix of these genetic patterns consistent with ancient hybridization of S. occidentalis and inland S. townsendi. Of the few highly-differentiated nDNA regions between inland S. townsendi and S. occidentalis, two of these regions (on chromosome 5 and Z, respectively) are also differentiated between coastal and inland S. townsendi, similar to the mtDNA pattern. These two nDNA regions are associated with mitochondrial fatty acid metabolism. Moreover, these nDNA regions are correlated with mtDNA ancestries among sites, a pattern consistent with mito-nuclear co-adaptation. Such mito-nuclear coevolution might be driven by climate-related selection, because the mito-nuclear ancestry is correlated with climatic conditions among sampling sites. These results suggest that cryptic differentiation in this species complex has been shaped by climate-correlated adaptation associated with mito-nuclear fatty acid metabolism.