Nuclear-mitochondrial conflict (cytonuclear incompatibility) is a specific form of Dobzhansky-Muller incompatibility previously shown to cause reproductive isolation in two yeast species. Here, we identified two new incompatible genes, MRS1 and AIM22, through a systematic study of F2 hybrid sterility caused by cytonuclear incompatibility in three closely related Saccharomyces species (S. cerevisiae, S. paradoxus, and S. bayanus). Mrs1 is a nuclear gene product required for splicing specific introns in the mitochondrial COX1, and Aim22 is a ligase encoded in the nucleus that is required for mitochondrial protein lipoylation. By comparing different species, our result suggests that the functional changes in MRS1 are a result of coevolution with changes in the COX1 introns. Further molecular analyses demonstrate that three nonsynonymous mutations are responsible for the functional differences of Mrs1 between these species. Functional complementation assays to determine when these incompatible genes altered their functions show a strong correlation between the sequence-based phylogeny and the evolution of cytonuclear incompatibility. Our results suggest that nuclear-mitochondrial incompatibility may represent a general mechanism of reproductive isolation during yeast evolution.