Aedes aegypti is an important disease vector and a major target of reproductive control efforts. We manipulated the opportunity for sexual selection in populations of Ae. aegypti by controlling the number of males competing for a single female. Populations exposed to higher levels of male competition rapidly evolved higher male competitive mating success relative to populations evolved in the absence of competition, with an evolutionary response visible after only five generations. We also detected correlated evolution in other important mating and life history traits, such as acoustic signalling, fecundity and body size. Our results indicate that there is ample segregating variation for determinants of male mating competitiveness in wild populations and that increased male mating success trades-off with other important life history traits. The mating conditions imposed on laboratory-reared mosquitoes are likely a significant determinant of male mating success in populations destined for release.