The perineuronal net (PNN) surrounds neurons in the central nervous system and is thought to regulate developmental plasticity. A few studies have shown an involvement of the PNN in hippocampal plasticity and memory storage in adult animals. In addition to the hippocampus, plasticity in the medial prefrontal cortex (mPFC) has been demonstrated to be critical for the storage of long-term memory, particularly memories for temporally separated events. In the present study, we examined the role of PNN in the acquisition and retention of memories for trace (in which the conditioned and unconditioned stimuli are temporally separated) and delayed (in which the conditioned and unconditioned stimuli overlap) fear conditioning in both the hippocampus and the mPFC. Consistent with a role for the hippocampus in memory storage in both delayed and trace fear conditioning, removal of hippocampal PNN disrupted contextual and trace fear memory. Disruption of the PNN in the mPFC impaired long-term trace and conditioned stimulus (CS)-elicited fear memory in the trace fear conditioning task. Interestingly, CS-elicited fear memory was also impaired when a delayed fear conditioning paradigm was used. These findings further support a role for the PNN in neural plasticity and implicate PNN-regulated plasticity in neocortical memory storage.