It is generally believed that fear extinction is a form of new learning that inhibits rather than erases previously acquired fear memories. Although this view has gained much support from behavioural and electrophysiological studies, the hypothesis that extinction causes the partial erasure of fear memories remains viable. Using transcranial two-photon microscopy, we investigated how neural circuits are modified by fear learning and extinction by examining the formation and elimination of postsynaptic dendritic spines of layer-V pyramidal neurons in the mouse frontal association cortex. Here we show that fear conditioning by pairing an auditory cue with a footshock increases the rate of spine elimination. By contrast, fear extinction by repeated presentation of the same auditory cue without a footshock increases the rate of spine formation. The degrees of spine remodelling induced by fear conditioning and extinction strongly correlate with the expression and extinction of conditioned fear responses, respectively. Notably, spine elimination and formation induced by fear conditioning and extinction occur on the same dendritic branches in a cue- and location-specific manner: cue-specific extinction causes formation of dendritic spines within a distance of two micrometres from spines that were eliminated after fear conditioning. Furthermore, reconditioning preferentially induces elimination of dendritic spines that were formed after extinction. Thus, within vastly complex neuronal networks, fear conditioning, extinction and reconditioning lead to opposing changes at the level of individual synapses. These findings also suggest that fear memory traces are partially erased after extinction.