Stress induces long-lasting changes in neuronal gene expression and cholinergic neurotransmission, but the underlying mechanism(s) are incompletely understood. Here, we report that chromatin structure and histone modifications are causally involved in this transcriptional memory. Specifically, the AChE gene encoding the acetylcholine-hydrolyzing enzyme acetylcholinesterase is known to undergo long-lasting transcriptional and alternative splicing changes after stress. In mice subjected to stress, we identified two alternative 5′ exons that were down-regulated after stress in the hippocampus, accompanied by reduced acetylation and elevated trimethylation of H3K9 at the corresponding promoter. These effects were reversed completely by daily administration of the histone deacetylase (HDAC) inhibitor sodium butyrate for 1 wk after stress. H3K9 hypoacetylation was associated with a selective, sodium butyrate-reversible promoter accumulation of HDAC4. Hippocampal suppression of HDAC4 in vivo completely abolished the long-lasting AChE-related and behavioral stress effects. Our findings demonstrate long-lasting stress-inducible changes in AChE’s promoter choices, identify the chromatin changes that support this long-term transcriptional memory, and reveal HDAC4 as a mediator of these effects in the hippocampus.