The DNA methylome of spermatozoa results from a unique epigenetic reprogramming crucial for chromatin compaction and the protection of the paternal genetic heritage. Although bull semen is widely used for artificial insemination (AI), little is known about the sperm epigenome in cattle. The purpose of this review is to synthetize recent work on the bull sperm methylome in light of the knowledge accumulated in humans and model species. We will address sperm-specific DNA methylation features and their potential evolutionary impacts, with particular emphasis on hypomethylated regions and repetitive elements. We will review recent examples of interindividual variability and intra-individual plasticity of the bull sperm methylome as related to fertility and age, respectively. Finally, we will address paternal methylome reprogramming after fertilization, as well as the mechanisms potentially involved in epigenetic inheritance, and provide some examples of disturbances that alter the dynamics of reprogramming in cattle. Because the selection of AI bulls is closely based on their genotypes, we will also discuss the complex interplay between sequence polymorphism and DNA methylation, which represents both a difficulty in addressing the role of DNA methylation in shaping phenotypes and an opportunity to better understand genome plasticity.