Cyto-nuclear incompatibility, a specific form of Dobzhansky-Muller incompatibility caused by incompatible alleles between mitochondrial and nuclear genomes, has been suggested to play a critical role during speciation. Several features of the mitochondrial genome (mtDNA), including high mutation rate, dynamic genomic structure, and uniparental inheritance, make mtDNA more likely to accumulate mutations in the population. Once mtDNA has changed, the nuclear genome needs to play catch-up due to the intimate interactions between these two genomes. In two populations, if cyto-nuclear co-evolution is driven in different directions, it may eventually lead to hybrid incompatibility. Although cyto-nuclear incompatibility has been observed in a wide range of organisms, it remains unclear what type of mutations drives the co-evolution. Currently, evidence supporting adaptive mutations in mtDNA remains limited. On the other hand, it has been known that some mutations allow mtDNA to propagate more efficiently but compromise the host fitness (described as selfish mtDNA). Arms races between such selfish mtDNA and host nuclear genomes can accelerate cyto-nuclear co-evolution and lead to a phenomenon called the Red Queen Effect. Here, we discuss how the Red Queen Effect may contribute to the frequent observation of cyto-nuclear incompatibility and be the underlying driving force of some human mitochondrial diseases.