Memory formation and storage require long-lasting changes in memory-related neuronal circuits. Recent evidence indicates that DNA methylation may serve as a contributing mechanism in memory formation and storage. These emerging findings suggest a role for an epigenetic mechanism in learning and long-term memory maintenance and raise apparent conundrums and questions. For example, it is unclear how DNA methylation might be reversed during the formation of a memory, how changes in DNA methylation alter neuronal function to promote memory formation, and how DNA methylation patterns differ between neuronal structures to enable both consolidation and storage of memories. Here we evaluate the existing evidence supporting a role for DNA methylation in memory, discuss how DNA methylation may affect genetic and neuronal function to contribute to behavior, propose several future directions for the emerging subfield of neuroepigenetics, and begin to address some of the broader implications of this work.