Mitochondria are essential organelles whose replication, development, and physiology are dependent upon coordinated gene interactions with both the mitochondrial and the nuclear genomes. The evolution of coadapted (CA) nuclear-mitochondrial gene combinations would be facilitated if such nuclear genes were located on the X-chromosome instead of on the autosomes because of the increased probability of cotransmission. Here, we test the prediction of the CA hypothesis by investigating the chromosomal distribution of nuclear genes that interact with mitochondria. Using the online genome database BIOMART, we compared the density of genes that have a mitochondrion cellular component annotation across chromosomes in 16 vertebrates. We find a strong and highly significant genomic pattern against the CA hypothesis: nuclear genes interacting with the mitochondrion are significantly underrepresented on the X-chromosome in mammals but not in birds. We interpret our findings in terms of sexual conflict as a mechanism that may generate the observed pattern. Our finding extends single-gene theory for the evolution of sexually antagonistic genes to nuclear-mitochondrial gene combinations.