Gaseous formaldehyde is an organic small molecule formed in the early stages of earth's evolution. Although toxic in high concentrations, formaldehyde plays an important role in cellular metabolism and, unexpectedly, is found even in the healthy brain. However, its pathophysiological functions in the brain are unknown. Here, we report that under physiological conditions, spatial learning activity elicits rapid formaldehyde generation from mitochondrial sarcosine dehydrogenase (SARDH). We find that elevated formaldehyde levels facilitate spatial memory formation by enhancing N-methyl-D-aspartate (NMDA) currents via the C232 residue of the NMDA receptor, but that high formaldehyde concentrations gradually inactivate the receptor by cross-linking NR1 subunits to NR2B. We also report that in mice with aldehyde dehydrogenase-2 (ALDH2) knockout, formaldehyde accumulation due to hypofunctional ALDH2 impairs memory, consistent with observations of Alzheimer's disease patients. We also find that formaldehyde deficiency caused by mutation of the mitochondrial SARDH gene in children with sarcosinemia or in mice with Sardh deletion leads to cognitive deficits. Hence, we conclude that endogenous formaldehyde regulates learning and memory via the NMDA receptor.