Extinction of classical fear conditioning is thought to involve activity-dependent potentiation of synaptic transmission in the medial prefrontal cortex (mPFC), resulting in the inhibition of amygdala-dependent fear responses. While many studies have addressed the mechanisms underlying extinction learning, it is unclear what determines whether extinction memory is consolidated or whether spontaneous recovery of the fear response occurs. Here we show, using a combined electrophysiological and immunocytochemical approach, that spontaneous recovery of conditioned fear in mice is associated with a prolonged expression of long-term depression of synaptic transmission in the mPFC and the failure of induction of the immediate-early genesc-Fos and zif268 in the mPFC and the basolateral nucleus of the amygdala. This suggests that coordinated activity-dependent changes in gene expression in the mPFC and the amygdala may underlie the formation of long-term fear extinction memory.