In many species, females display preferences for extreme male signal traits, but it has not been determined if such preferences evolve as a consequence of females gaining genetic benefits from exercising choice. If females prefer extreme male traits because they indicate male genetic quality that will enhance the fitness of offspring, a genetic correlation will evolve between female preference genes and genes that confer offspring fitness. We show that females of Drosophila serrata prefer extreme male cuticular hydrocarbon (CHC) blends, and that this preference affects offspring fitness. Female preference is positively genetically correlated with offspring fitness, indicating that females have gained genetic benefits from their choice of males. Despite male CHCs experiencing strong sexual selection, the genes underlying attractive CHCs also conferred lower offspring fitness, suggesting a balance between sexual selection and natural selection may have been reached in this population.