Memory is stored in neural networks via changes in synaptic strength mediated in part by NMDA-dependent long-term potentiation (LTP). There is evidence that entorhinal cortex enables neocortical neuroplasticity through cholecystokinin (CCK)-containing neocortical projections. Here we show that a CCKB antagonist blocks high-frequency stimulation (HFS)-induced LTP in the auditory cortex, whereas local infusion of CCK induces LTP. CCK-/- mice lacked neocortical LTP and showed deficits in a cue-cue associative learning paradigm; administration of CCK rescued associative learning. HFS of CCK-containing entorhino-neocortical projection neurons in anesthetized mice enabled cue-cue associative learning. Furthermore, when one cue was pre-conditioned to footshock, the mouse showed a freezing response to the other cue, indicating that the mice had formed an association. HFS-induced neocortical LTP was completely blocked by either NMDA antagonist or CCK-BR antagonist, while application of either NMDA or CCK induced LTP after low-frequency stimulation (LFS). Moreover, in the presence of CCK LTP was still induced, even after blockade of NMDA receptors. Local application of NMDA induced CCK release in the neocortex. To identify how NMDA receptor switches LTP, a stimulation protocol of 25 pulse-pairs was adopted to replace HFS; NMDA-dependent LTP was induced with the inter-pulse intervals between 10 and 100 ms, but not with those of 5 and 200 ms. LTP-mediated plasticity was linked to localization of the NMDA receptor subunit NR2a on cortical CCK terminals originating in the entorhinal cortex. These novel findings suggest that presynaptic NMDA receptors on CCK terminals control the release of CCK, which enables neocortical LTP and formation of cue-cue associative memory.