Despite heritable variation for univariate sexually selected traits, recent analyses exploring multivariate traits find evidence consistent with the lek paradox in showing no genetic variation available to choosy females, and therefore no genetic benefits of choice. We used the preferences of Drosophila melanogaster females to exert bidirectional selection on competitive male mating success to test for the presence and nature of genetic variation underlying this multivariate trait. Male mating success diverged between selection regimens, and flies from success-selected lines had a smaller burden of deleterious, recessive mutations that affect egg-to-adult viability, were better sperm competitors (sperm offence), and did not demonstrate reduced desiccation resistance or components of female fitness (traits thought to trade off with attractiveness) relative to flies from failure-selected populations. Mating success remained subject to inbreeding depression in success-selected lines, suggesting that variation in mating success remains, thanks to numerous genes of small effect. Together, our results provide unique evidence for the evolutionary divergence in male mating success, demonstrating that genetic variation is not exhausted along the axis of precopulatory sexual selection and that female mating biases align with the avoidance of bad genes.