A common pattern observed in molecular evolution is that reproductive genes tend to evolve rapidly. However, most previous studies documenting this rapid evolution are based on genes expressed in just a few male reproductive organs. In mammals, sperm become motile and capable of fertilization only after leaving the testis, during their transit through the epididymis. Thus, genes expressed in the epididymis are expected to play important roles in male fertility. Here, we performed evolutionary genetic analyses on the epididymal transcriptome of mice. Overall, epididymis-expressed genes showed evidence of strong evolutionary constraint, a finding that contrasts with most previous analyses of genes expressed in other male reproductive organs. However, a subset of epididymis-specialized, secreted genes showed several signatures of adaptive evolution, including an increased rate of nonsynonymous evolution. Furthermore, this subset of genes was overrepresented on the X chromosome. Immunity and protein modification functions were significantly overrepresented among epididymis-specialized, secreted genes. These analyses identified a group of genes likely to be important in male reproductive success.