Proper mitochondrial activity depends upon proteins encoded by genes in the nuclear and mitochondrial genomes that must interact functionally and physically in a precisely coordinated manner. Consequently, mito-nuclear allelic interactions are thought to be of crucial importance on an evolutionary scale, as well as for manifestation of essential biological phenotypes, including those directly relevant to human disease. Nonetheless, detailed molecular understanding of mito-nuclear interactions is still lacking, and definitive examples of such interactions in vivo are sparse. Here we describe the characterization of a mutation in Drosophila ND23, a nuclear gene encoding a highly conserved subunit of mitochondrial complex 1. This characterization led to the discovery of a mito-nuclear interaction that affects the ND23 mutant phenotype. ND23 mutants exhibit reduced lifespan, neurodegeneration, abnormal mitochondrial morphology, and decreased ATP levels. These phenotypes are similar to those observed in patients with Leigh syndrome, which is caused by mutations in a number of nuclear genes that encode mitochondrial proteins, including the human ortholog of ND23 A key feature of Leigh syndrome, and other mitochondrial disorders, is unexpected and unexplained phenotypic variability. We discovered that the phenotypic severity of ND23 mutations varies depending on the maternally inherited mitochondrial background. Sequence analysis of the relevant mitochondrial genomes identified several variants that are likely candidates for the phenotypic interaction with mutant ND23, including a variant affecting a mitochondrially encoded component of complex I. Thus, our work provides an in vivo demonstration of the phenotypic importance of mito-nuclear interactions in the context of mitochondrial disease.