Dietary magnesium (Mg2+) 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 Mg2+ feeding also enhances long-term memory in Drosophila. Normal and Mg2+-enhanced fly memory appears independent of NMDA receptors in the mushroom body and instead requires expression of a conserved CNNM-type Mg2+-efflux transporter encoded by the unextended (uex) gene. UEX contains a putative cyclic nucleotide-binding homology domain and its mutation separates a vital role for uex 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 Mg2+. We propose that regulated neuronal Mg2+ efflux is critical for normal and Mg2+-enhanced memory.