Most cell functions are carried out by interacting factors, thus underlying the functional importance of genetic interactions between genes, termed epistasis. Epistasis could be under strong selective pressures especially in conditions where the mutation rate of one of the interacting partners notably differs from the other. Accordingly, the order of magnitude higher mitochondrial DNA (mtDNA) mutation rate as compared to the nuclear DNA (nDNA) of all tested animals, should influence systems involving mitochondrial-nuclear (mito-nuclear) interactions. Such is the case of the energy producing oxidative phosphorylation (OXPHOS) and mitochondrial translational machineries which are comprised of factors encoded by both the mtDNA and the nDNA. Additionally, the mitochondrial RNA transcription and mtDNA replication systems are operated by nDNA-encoded proteins that bind mtDNA regulatory elements. As these systems are central to cell life there is strong selection toward mito-nuclear co-evolution to maintain their function. However, it is unclear whether (A) mito-nuclear co-evolution befalls only to retain mitochondrial functions during evolution or, also, (B) serves as an adaptive tool to adjust for the evolving energetic demands as species' complexity increases. As the first step to answer these questions we discuss evidence of both negative and adaptive (positive) selection acting on the mtDNA and nDNA-encoded genes and the effect of both types of selection on mito-nuclear interacting factors. Emphasis is given to the crucial role of recurrent ancient (nodal) mutations in such selective events. We apply this point-of-view to the three available types of mito-nuclear co-evolution: protein-protein (within the OXPHOS system), protein-RNA (mainly within the mitochondrial ribosome), and protein-DNA (at the mitochondrial replication and transcription machineries).