The yellow fever mosquito, Aedes aegypti, mates in flight as part of ephemeral aggregations termed swarms. Swarms contain many more males than females, and males are thought to be subject to intense sexual selection.1,2 However, which male traits are involved in mating success and the genetic basis of these traits remains unclear. We used an experimental evolution approach to measure genome-wide responses of Ae. aegypti evolved in the presence and absence of sexual selection. These data revealed for the first time how sexual selection shapes the genome of this important species. We found that populations evolved under sexual selection retained greater genetic similarity to the ancestral population and a higher effective population size than populations evolving without sexual selection. When we compared evolutionary regimes, we found that genes associated with chemosensation responded rapidly to the elimination of sexual selection. Knockdown of one high-confidence candidate gene identified in our analysis significantly decreased male insemination success, further suggesting that genes related to male sensory perception are under sexual selection. Several mosquito control technologies involve the release of males from captive populations into the wild. For these interventions to work, a released male must compete against wild males to successfully inseminate a female. Our results suggest that maintaining the intensity of sexual selection in captive populations used in mass-releases is important for sustaining both male competitive ability and overall genetic similarity to field populations.