Sexual selection, through intra-male competition or female choice, is assumed to be a source of strong and sustained directional selection in the wild. In the presence of such strong directional selection, alleles enhancing a particular trait are predicted to become fixed within a population, leading to a decrease in the underlying genetic variation. However, there is often considerable genetic variation underlying sexually selected traits in wild populations, and consequently, this phenomenon has become a long-discussed issue in the field of evolutionary biology. In wild Soay sheep, large horns confer an advantage in strong intra-sexual competition, yet males show an inherited polymorphism for horn type and have substantial genetic variation in their horn size. Here we show that most genetic variation in this trait is maintained by a trade-off between natural and sexual selection at a single gene, relaxin-like receptor 2 (RXFP2). We found that an allele conferring larger horns, Ho(+), is associated with higher reproductive success, whereas a smaller horn allele, Ho(P), confers increased survival, resulting in a net effect of overdominance (that is, heterozygote advantage) for fitness at RXFP2. The nature of this trade-off is simple relative to commonly proposed explanations for the maintenance of sexually selected traits, such as genic capture ('good genes') and sexually antagonistic selection. Our results demonstrate that by identifying the genetic architecture of trait variation, we can determine the principal mechanisms maintaining genetic variation in traits under strong selection and explain apparently counter-evolutionary observations.