In most macaques, females are philopatric and males migrate from their natal ranges, which results in pronounced divergence of mitochondrial genomes within and among species. We therefore predicted that some nuclear genes would have to acquire compensatory mutations to preserve compatibility with diverged interaction partners from the mitochondria. We additionally expected that these sex-differences would have distinctive effects on gene flow in the X and autosomes. Using new genomic data from 29 individuals from eight species of Southeast Asian macaque, we identified evidence of natural selection associated with mitonuclear interactions, including extreme outliers of interspecies differentiation and metrics of positive selection, low intraspecies polymorphism and atypically long runs of homozygosity associated with nuclear-encoded genes that interact with mitochondria-encoded genes. In one individual with introgressed mitochondria, we detected a small but significant enrichment of autosomal introgression blocks from the source species of her mitochondria that contained genes which interact with mitochondria-encoded loci. Our analyses also demonstrate that sex-specific demography sculpts genetic exchange across multiple species boundaries. These findings show that behaviour can have profound but indirect effects on genome evolution by influencing how interacting components of different genomic compartments (mitochondria, the autosomes and the sex chromosomes) move through time and space.