One of the most exciting discoveries in the learning and memory field in the past two decades is the observation that active regulation of gene expression is necessary for experience to trigger lasting functional and behavioral change, in a wide variety of species, including humans. Thus, as opposed to the traditional view of 'nature' (genes) being separate from 'nurture' (environment and experience), it is now clear that experience actively drives alterations in central nervous system (CNS) gene expression in an ongoing fashion, and that the resulting transcriptional changes are necessary for experience to trigger altered long-term behavior. In parallel over the past decade, epigenetic mechanisms, including regulation of chromatin structure and DNA methylation, have been shown to be potent regulators of gene transcription in the CNS. In this review, we describe data supporting the hypothesis that epigenetic molecular mechanisms, especially DNA methylation and demethylation, drive long-term behavioral change through active regulation of gene transcription in the CNS. Specifically, we propose that epigenetic molecular mechanisms underlie the formation and stabilization of context- and cue-triggered fear conditioning based in the hippocampus and amygdala, a conclusion reached in a wide variety of studies using laboratory animals. Given the relevance of cued and contextual fear conditioning to post-traumatic stress, by extension we propose that these mechanisms may contribute to post-traumatic stress disorder (PTSD) in humans. Moreover, we speculate that epigenetically based pharmacotherapy may provide a new avenue of drug treatment for PTSD-related cognitive and behavioral function.