Evolutionary theory predicts the depletion of genetic variation in natural populations as a result of the effects of selection, but genetic variation is nevertheless abundant for many traits that are under directional or stabilizing selection. Evolutionary geneticists commonly try to explain this paradox with mechanisms that lead to a balance between mutation and selection. However, theoretical predictions of equilibrium genetic variance under mutation-selection balance are usually lower than the observed values, and the reason for this is unknown. The potential role of sexually antagonistic selection in maintaining genetic variation has received little attention in this debate, surprisingly given its potential ubiquity in dioecious organisms. At fitness-related loci, a given genotype may be selected in opposite directions in the two sexes. Such sexually antagonistic selection will reduce the otherwise-expected positive genetic correlation between male and female fitness. Both theory and experimental data suggest that males and females of the same species may have divergent genetic optima, but supporting data from wild populations are still scarce. Here we present evidence for sexually antagonistic fitness variation in a natural population, using data from a long-term study of red deer (Cervus elaphus). We show that male red deer with relatively high fitness fathered, on average, daughters with relatively low fitness. This was due to a negative genetic correlation between estimates of fitness in males and females. In particular, we show that selection favours males that carry low breeding values for female fitness. Our results demonstrate that sexually antagonistic selection can lead to a trade-off between the optimal genotypes for males and females; this mechanism will have profound effects on the operation of selection and the maintenance of genetic variation in natural populations.