Strict maternal inheritance renders the mitochondrial genome susceptible to accumulating mutations that harm males, but are otherwise benign or beneficial for females. This ‘mother's curse’ effect can degrade male survival and fertility if unopposed by counteracting evolutionary processes. Coadaptation between nuclear and mitochondrial genomes—with nuclear genes evolving to compensate for male-harming mitochondrial substitutions—may ultimately resolve mother's curse. However, males are still expected to incur a transient fitness cost during mito-nuclear coevolution, and it remains unclear how severe such costs should be. We present a population genetic analysis of mito-nuclear coadaptation to resolve mother's curse effects, and show that the magnitude of the ‘male mitochondrial load’—the negative impact of mitochondrial substitutions on male fitness components—may be large, even when genetic variation for compensatory evolution is abundant. We also find that the male load is surprisingly sensitive to population size: male fitness costs of mito-nuclear coevolution are particularly pronounced in both small and large populations, and minimized in populations of intermediate size. Our results reveal complex interactions between demography and genetic constraints during the resolution of mother's curse, suggesting potentially widespread species differences in susceptibility to mother's curse effects.