Adaptive mate choice by females is an important component of sexual selection in many species. The evolutionary consequences of male mate preferences, however, have received relatively little study, especially in the context of sexual conflict, where males often harm their mates. Here, we describe a new and counterintuitive cost of sexual selection in species with both male mate preference and sexual conflict via antagonistic male persistence: male mate choice for high-fecundity females leads to a diminished rate of adaptive evolution by reducing the advantage to females of expressing beneficial genetic variation. We then use a Drosophila melanogaster model system to experimentally test the key prediction of this theoretical cost: that antagonistic male persistence is directed toward, and harms, intrinsically higher-fitness females more than it does intrinsically lower-fitness females. This asymmetry in male persistence causes the tails of the population's fitness distribution to regress towards the mean, thereby reducing the efficacy of natural selection. We conclude that adaptive male mate choice can lead to an important, yet unappreciated, cost of sex and sexual selection.