Phenotypic adaptations may be the result of changes in gene structure or gene regulation, but little is known about the evolution of gene expression. In addition, it is unclear whether the same selective forces may operate at both levels simultaneously. Reproductive proteins evolve rapidly, but the underlying selective forces promoting such rapid changes are still a matter of debate. In particular, the role of sexual selection in driving positive selection among reproductive proteins remains controversial, whereas its potential influence on changes in promoter regions has not been explored. Protamines are responsible for maintaining DNA in a compacted form in chromosomes in sperm and the available evidence suggests that they evolve rapidly. Because protamines condense DNA within the sperm nucleus, they influence sperm head shape. Here, we examine the influence of sperm competition upon protamine 1 and protamine 2 genes and their promoters, by comparing closely related species of Mus that differ in relative testes size, a reliable indicator of levels of sperm competition. We find evidence of positive selection in the protamine 2 gene in the species with the highest inferred levels of sperm competition. In addition, sperm competition levels across all species are strongly associated with high divergence in protamine 2 promoters that, in turn, are associated with sperm swimming speed. We suggest that changes in protamine 2 promoters are likely to enhance sperm swimming speed by making sperm heads more hydrodynamic. Such phenotypic changes are adaptive because sperm swimming speed may be a major determinant of fertilization success under sperm competition. Thus, when species have diverged recently, few changes in gene-coding sequences are found, while high divergence in promoters seems to be associated with the intensity of sexual selection.