Although it has been shown that changes in DNA methylation are crucial for memory formation, it is still unknown what the specific role and dynamics of DNA methylation and its targets are in memory formation. Using the honeybee as a learning model we first looked at the role of DNA methyltransferases (Dnmts) in different memory phases. We trained bees to associate a specific odour with a sugar reward and inhibited Dnmts before or after training. During the memory retention test bees were presented with the learned and a new odour. We showed that associative odour-specific long-term memory is dependent on Dnmt function. Odour-specific memory is the ability of bees to form a memory of a specific odour and not generalize to other odours. This ability was impaired if Dnmts were inhibited and resulted in loss of odour memory fidelity. We also investigated the expression of memory related target genes 24 hours after training, finding several of them upregulated after Dnmt inhibition in trained bees. Interestingly, Dnmt3 was upregulated in response to Dnmt inhibition after training, suggesting that Dnmt3 is auto-regulated. We further looked at differentially methylated regions (DMRs) due to long-term memory formation in those target genes using Sequenome Mass Spectrometry. We found DMRs in promoter, exon and intron regions of our target genes. Because memory formation and its regulation is a temporally dynamic process, we also examined the expression of Dnmts over time for the first 6 hours and at 24 hours after training. Dnmt1a/b and Dnmt3 were upregulated 24 hours after training. In conclusion, our study shows that long-term memory formation is a temporally dynamic process, which is, among other mechanisms, regulated by Dnmts, with Dnmt3 likely to be auto-regulated and several memory related genes being differentially methylated after training.