Long-term memory (LTM) formation has been linked with functional strengthening of existing synapses and other processes including de novo synaptogenesis. However, it is unclear whether synaptogenesis can contribute to LTM formation. Here, using α-calcium/calmodulin kinase II autophosphorylation-deficient (T286A) mutants, we demonstrate that when functional strengthening is severely impaired, contextual LTM formation is linked with training-induced PSD95 up-regulation followed by persistent generation of multiinnervated spines, a type of synapse that is characterized by several presynaptic terminals contacting the same postsynaptic spine. Both PSD95 up-regulation and contextual LTM formation in T286A mutants required signaling by the mammalian target of rapamycin (mTOR). Furthermore, we show that contextual LTM resists destabilization in T286A mutants, indicating that LTM is less flexible when synaptic strengthening is impaired. Taken together, we suggest that activation of mTOR signaling, followed by overexpression of PSD95 protein and synaptogenesis, contributes to formation of invariant LTM when functional strengthening is impaired.