Dietary magnesium (Mg) supplementation can enhance memory in young and aged rats. Memory-enhancing capacity was largely ascribed to increases in hippocampal synaptic density and elevated expression of the NR2B subunit of the NMDA-type glutamate receptor. Here we show that Mg feeding also enhances long-term memory in . Normal and Mg-enhanced fly memory appears independent of NMDA receptors in the mushroom body and instead requires expression of a conserved CNNM-type Mg-efflux transporter encoded by the () gene. UEX contains a putative cyclic nucleotide-binding homology domain and its mutation separates a vital role for from a function in memory. Moreover, UEX localization in mushroom body Kenyon cells (KCs) is altered in memory-defective flies harboring mutations in cAMP-related genes. Functional imaging suggests that UEX-dependent efflux is required for slow rhythmic maintenance of KC Mg. We propose that regulated neuronal Mg efflux is critical for normal and Mg-enhanced memory.