Gadd45-mediated DNA demethylation mechanisms have been implicated in the process of memory formation. However, the transcriptional mechanisms involved in the regulation of Gadd45 gene expression during memory formation remain unexplored. NF-κB (nuclear factor kappa-light-chain-enhancer of activated B cells) controls transcription of genes in neurons and is a critical regulator of synaptic plasticity and memory formation. In silico analysis revealed several NF-κB (p65/RelA and cRel) consensus sequences within the Gadd45β gene promoter. Whether NF-κB activity regulates Gadd45 expression and associated DNA demethylation in neurons during memory formation is unknown. Here, we found that learning in a fear conditioning paradigm increased Gadd45β gene expression and brain-derived neurotrophic factor (BDNF) DNA demethylation in area CA1 of the hippocampus, both of which were prevented with pharmacological inhibition of NF-κB activity. Further experiments found that conditional mutations in p65/RelA impaired fear memory formation but did not alter changes in Gadd45β expression. The learning-induced increases in Gadd45β mRNA levels, Gadd45β binding at the BDNF gene and BDNF DNA demethylation were blocked in area CA1 of the c-rel knockout mice. Additionally, local siRNA-mediated knockdown of c-rel in area CA1 prevented fear conditioning-induced increases in Gadd45β expression and BDNF DNA demethylation, suggesting that c-Rel containing NF-κB transcription factor complex is responsible for Gadd45β regulation during memory formation. Together, these results support a novel transcriptional role for NF-κB in regulation of Gadd45β expression and DNA demethylation in hippocampal neurons during fear memory.