Memory is created by several interlinked processes in the brain, some of which require long-term gene regulation. Epigenetic mechanisms are likely candidates for regulating memory-related genes. Among these, DNA methylation is known to be a long lasting genomic mark and may be involved in the establishment of long-term memory. Here we demonstrate that DNA methyltransferases, which induce and maintain DNA methylation, are involved in a particular aspect of associative long-term memory formation in honeybees, but are not required for short-term memory formation. While long-term memory strength itself was not affected by blocking DNA methyltransferases, odor specificity of the memory (memory discriminatory power) was. Conversely, perceptual discriminatory power was normal. These results suggest that different genetic pathways are involved in mediating the strength and discriminatory power of associative odor memories and provide, to our knowledge, the first indication that DNA methyltransferases are involved in stimulus-specific associative long-term memory formation.