DNA methylation and demethylation are epigenetic mechanisms involved in memory formation. In honey bees DNA methyltransferase (Dnmt) function is necessary for long-term memory to be stimulus specific (i.e. to reduce generalization). So far, however, it remains elusive which genes are targeted and what the time-course of DNA methylation is during memory formation. Here, we analyse how DNA methylation affects memory retention, gene expression, and differential methylation in stimulus-specific olfactory long-term memory formation. Out of 30 memory-associated genes investigated here, 9 were upregulated following Dnmt inhibition in trained bees. These included Dnmt3 suggesting a negative feedback loop for DNA methylation. Within these genes also the DNA methylation pattern changed during the first 24 hours after training. Interestingly, this was accompanied by sequential activation of the DNA methylation machinery (i.e. Dnmts and Tet). In sum, memory formation involves a temporally complex epigenetic regulation of memory-associated genes that facilitates stimulus specific long-term memory in the honey bee.