Mitochondria perform many key roles in their eukaryotic hosts, from integrating signaling pathways through to modulating whole organism phenotypes. The > 1 billion years of nuclear and mitochondrial gene co-evolution has necessitated coordinated expression of gene products from both genomes that maintain mitochondrial, and more generally, eukaryotic cellular function. How mitochondrial DNA (mtDNA) variation modifies host fitness has proved a challenging question but has profound implications for evolutionary and medical genetics. In Drosophila, we have previously shown that recently diverged mtDNA haplotypes within-species can have more impact on organismal phenotypes than older, deeply diverged haplotypes from different species. Here, we tested the effects of mtDNA haplotype variation on gene expression in Drosophila under standardized conditions. Using the Drosophila Genetic Reference Panel (DGRP), we constructed a panel of mitonuclear genotypes that consists of factorial variation in nuclear and mtDNA genomes, with mtDNAs originating in D. melanogaster (2x haplotypes) and D. simulans (2x haplotypes). We show that mtDNA haplotype variation unequivocally alters nuclear gene expression in both females and males, and mitonuclear interactions are pervasive modifying factors for gene expression. There was appreciable overlap between the sexes for mtDNA-sensitive genes, and considerable transcriptional variation attributed to particular mtDNA contrasts. These genes are generally found in low-connectivity gene co-expression networks, occur in gene clusters along chromosomes, are often flanked by non-coding RNA, and are under-represented among housekeeping genes. Finally, we identify the giant (gt) transcription factor motif as a putative regulatory sequence associated with mtDNA-sensitive genes. There are predictive conditions for nuclear genes that are influenced by mtDNA variation.