Methylation of DNA is an epigenetic mechanism that influences patterns of gene expression. DNA methylation marks contribute to adaptive phenotypic variation but are erased during development. The role of DNA methylation in adaptive evolution is therefore unclear. We propose that environmentally-induced DNA methylation causes phenotypic heterogeneity that provides a substrate for selection via forces that act on the epigenetic machinery. For example, selection can alter environmentally-induced methylation of DNA by acting on the molecular mechanisms used for the genomic targeting of DNA methylation. Another possibility is that specific methylation marks that are environmentally-induced, yet non-heritable, could influence preferential survival and lead to consistent methylation of the same genomic regions over time. As methylation of DNA is known to increase the likelihood of cytosine-to-thymine transitions, non-heritable adaptive methylation marks can drive an increased likelihood of mutations targeted to regions that are consistently marked across several generations. Some of these mutations could capture, genetically, the phenotypic advantage of the epigenetic mark. Thereby, selectively favored transitory alterations in the genome invoked by DNA methylation could ultimately become selectable genetic variation through mutation. We provide evidence for these concepts using examples from different taxa, but focus on experimental data on large-scale DNA sequencing that expose between-group genetic variation after bidirectional selection on honeybees, Apis mellifera.