DNA forms conformational states beyond the right-handed double helix; however, the functional relevance of these noncanonical structures in the brain remains unknown. Here we show that, in the prefrontal cortex of mice, the formation of one such structure, Z-DNA, is involved in the regulation of extinction memory. Z-DNA is formed during fear learning and reduced during extinction learning, which is mediated, in part, by a direct interaction between Z-DNA and the RNA-editing enzyme Adar1. Adar1 binds to Z-DNA during fear extinction learning, which leads to a reduction in Z-DNA at sites where Adar1 is recruited. Knockdown of Adar1 leads to an inability to modify a previously acquired fear memory and blocks activity-dependent changes in DNA structure and RNA state-effects that are fully rescued by the introduction of full-length Adar1. These findings suggest a new mechanism of learning-induced gene regulation that is dependent on proteins that recognize alternate DNA structure states, which are required for memory flexibility.