Structural changes in brain circuits active during learning are thought to be important for long-term memory storage. If these changes support long-term information storage, they might be expected to be present at distant time points after learning, as well as to be specific to the circuit activated with learning, and sensitive to the contingencies of the behavioral paradigm. Here, we show such changes in the hippocampus as a result of contextual fear conditioning. There were significantly fewer spines specifically on active neurons of fear-conditioned mice. This spine loss did not occur in homecage mice or in mice exposed to the training context alone. Mice exposed to unpaired shocks showed a generalized reduction in spines. These learning-related changes in spine density could reflect a direct mechanism of encoding or alternately could reflect a compensatory adaptation to previously described enhancement in transmission due to glutamate receptor insertion.