DNA methylation is an important epigenetic modification that mediates diverse processes such as cellular differentiation, phenotypic plasticity, and genomic imprinting. Mounting evidence suggests that local DNA sequence variation can be associated with particular DNA methylation states, indicating that the interplay between genetic and epigenetic factors may contribute synergistically to the phenotypic complexity of organisms. Social insects such as ants, bees, and wasps have extensive phenotypic plasticity manifested in their different castes, and this plasticity has been associated with variation in DNA methylation. Yet, the influence of genetic variation on DNA methylation state remains mostly unknown. Here we examine the importance of sequence-specific methylation at the genome-wide level, using whole-genome bisulfite sequencing of the semen of individual honey bee males. We find that individual males harbor unique DNA methylation patterns in their semen, and that genes that are more variable at the epigenetic level are also more likely to be variable at the genetic level. DNA sequence variation can affect DNA methylation by modifying CG sites directly, but can also be associated with local variation in cis that is not CG-site specific. We show that covariation in sequence polymorphism and DNA methylation state contributes to the individual-specificity of epigenetic marks in social insects, which likely promotes their retention across generations, and their capacity to influence evolutionary adaptation.