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. Yet, the genomic architecture of mitonuclear incompatibilities has rarely been elucidated. We employ an experimental evolution approach starting with low-fitness F2 interpopulation hybrids of the copepod Tigriopus californicus, in which frequencies of compatible and incompatible nuclear alleles change in response to a alternate 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 three replicates of each reciprocal cross, but markedly different patterns between mitochondrial backgrounds. 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.