Induction of long-term potentiation and application of short periods of anoxia/hypoglycemia result in the growth of dendritic filopodia and formation of new spines. Here we investigated whether these conditions also affected the morphology of presynaptic structures. Using confocal imaging of DiI-labeled axons, electron microscopy, and stereological analyses, we show that short anoxia/hypoglycemia and theta burst stimulation induced rapid, calcium-dependent growth of presynaptic filopodia-like protrusions and remodeling of presynaptic varicosities. Three-dimensional reconstruction of axonal outgrowths revealed that, within 30 min, they made contacts and triggered the formation of a postsynaptic density on the target cell. Interestingly, these axonal filopodia first established synapses with the dendritic shaft and later mostly with spines. They also contributed to the formation of multi-innervated spines. Because these presynaptic growth mechanisms depended on NMDA receptor activation, we investigated whether a diffusing messenger could be involved. We found that blockade of nitric oxide synthase prevented these changes, and conversely, a nitric oxide donor could reproduce them. A model is presented that proposes that activation of NMDA receptors and subsequent release of nitric oxide could trigger the growth of presynaptic filopodia, which, in turn, play an active role in synaptogenesis and spine formation.