Extreme differences between the sexes are usually explained by intense sexual selection on male weapons or ornaments. Sexually antagonistic genes, with a positive effect on male traits but a negative effect on female fitness, create a negative inter-sexual correlation for fitness (sexual conflict). However, such antagonism might not be apparent if sexually selected male traits are condition-dependent, and condition elevates female fitness. Here we reveal a surprising positive genetic correlation between male weaponry and female fecundity. Using mite lines that had previously been through 13 generations of selection on male weapons (fighting legs), we investigated correlated evolution in female fecundity. Females from lines under positive selection for weapons (up lines) evolved higher fecundity, despite evolving costly, thicker legs. This is likely because male mites have condition-dependent weaponry that increases our ability to indirectly select on male condition. Alleles with positive effects on condition in both sexes could have generated this correlation because: the up lines evolved a higher proportion of fighters and there were positive correlations between weapon size and the male morph and sex ratios of the offspring. This positive inter-sexual genetic correlation should boost the evolution of male weapons and extreme sex differences.