Epigenetic mechanisms such as DNA methylation and histone methylation are critical regulators of gene transcription changes during memory consolidation. However, it is unknown how these epigenetic modifications coordinate control of gene expression following reactivation of a previously consolidated memory. Here, we found that retrieval of a recent contextual fear conditioned memory increased global levels of H3 lysine 4-trimethylation (H3K4me3) and DNA 5-hydroxymethylation (5hmC) in area CA1 of the dorsal hippocampus. Further experiments revealed increased levels of H3K4me3 and DNA 5hmC within a CpG-enriched coding region of the Npas4, but not c-fos, gene. Intriguingly, retrieval of a 30-day old memory increased H3K4me3 and DNA 5hmC levels at a CpG-enriched coding region of c-fos, but not Npas4, in the anterior cingulate cortex, suggesting that while these two epigenetic mechanisms co-occur following the retrieval of a recent or remote memory, their gene targets differ depending on the brain region. Additionally, we found that in vivo siRNA-mediated knockdown of the H3K4me3 methyltransferase Mll1 in CA1 abolished retrieval-induced increases in DNA 5hmC levels at the Npas4 gene, suggesting that H3K4me3 couples to DNA 5hmC mechanisms. Consistent with this, loss of Mll1 prevented retrieval-induced increases in Npas4 mRNA levels in CA1 and impaired fear memory. Collectively, these findings suggest an important link between histone methylation and DNA hydroxymethylation mechanisms in the epigenetic control of de novo gene transcription triggered by memory retrieval.