Sperm competition can drive rapid evolution of male reproductive traits, but it remains unclear how variation in sperm competition intensity shapes phenotypic and molecular diversity across clades. Old World mice and rats (subfamily Murinae) comprise a rapid radiation and exhibit incredible diversity in sperm morphology and production. We combined phenotype and sequence data to model the evolution of reproductive traits and genes across 78 murine species. We identified several shifts towards smaller relative testes mass, a trait reflective of reduced sperm competition. Several sperm traits were associated with relative testes mass, suggesting that mating system evolution likely selects for convergent traits related to sperm competitive ability. Molecular evolutionary rates of spermatogenesis proteins also correlated with relative testes mass, but in an unexpected direction. We predicted that sperm competition would result in rapid divergence among species with large relative testes mass, but instead found that many spermatogenesis genes evolve more rapidly in species with smaller relative testes mass due to relaxed purifying selection. While some reproductive genes evolved under positive selection, relaxed selection played a greater role underlying rapid evolution in small testes species. Our work demonstrates that sexual selection can impose strong purifying selection shaping the evolution of male reproduction.