Decreased male fertility is a big concern in both human society and the livestock industry. Sperm DNA methylation is commonly believed to be associated with male fertility. However, due to the lack of accurate male fertility records (i.e., limited mating times), few studies have investigated the comprehensive impacts of sperm DNA methylation on male fertility in mammals. In this study, we generated 10 sperm DNA methylomes and performed a preliminary correlation analysis between signals from sperm DNA methylation and signals from large-scale (n = 27,214) genome-wide association studies (GWAS) of 35 complex traits (including 12 male fertility-related traits). We detected genomic regions, which experienced DNA methylation alterations in sperm and were associated with aging and extreme fertility phenotypes (e.g., sire-conception rate or SCR). In dynamic hypomethylated regions (HMRs) and partially methylated domains (PMDs), we found genes (e.g., HOX gene clusters and microRNAs) that were involved in the embryonic development. We demonstrated that genomic regions, which gained rather than lost methylations during aging, and in animals with low SCR were significantly and selectively enriched for GWAS signals of male fertility traits. Our study discovered 16 genes as the potential candidate markers for male fertility, including SAMD5 and PDE5A. Collectively, this initial effort supported a hypothesis that sperm DNA methylation may contribute to male fertility in cattle and revealed the usefulness of functional annotations in enhancing biological interpretation and genomic prediction for complex traits and diseases.