Reproductive isolation is often achieved when genes that are neutral or beneficial in their genomic background become functionally incompatible in a foreign genome, causing inviability, sterility or low fitness in hybrids. Recent studies suggest that mitonuclear interactions are among the initial incompatibilities to evolve at early stages of population divergence across taxa. Yet, it is unclear whether mitonuclear incompatibilities involve few or many regions in the nuclear genome. We employ an experimental evolution approach starting with unfit F2 interpopulation hybrids of the copepod Tigriopus californicus, in which compatible and incompatible nuclear alleles compete in a fixed mitochondrial background. After about nine generations, we observe a generalized increase in population size and in survivorship, suggesting efficiency of selection against maladaptive phenotypes. Whole genome sequencing of evolved populations showed some consistent allele frequency changes across the three replicates of each reciprocal cross, but markedly different patterns between mitochondrial background. In only a few regions (~6.5% of the genome), the same parental allele was overrepresented irrespective of the mitochondrial background. About 33% of the genome shows allele frequency changes consistent with divergent selection, with the location of these genomic regions strongly differing between mitochondrial backgrounds. The dominant allele matches the mitochondrial background in 87 and 89% of these genomic regions, consistent with mitonuclear coadaptation. These results suggest that mitonuclear incompatibilities have a complex polygenic architecture that differs between populations, potentially generating genome wide barriers to gene flow between closely related taxa.