Age-dependent memory impairment is known to occur in several organisms, including Drosophila, mouse and human. However, the fundamental cellular mechanisms that underlie these impairments are still poorly understood, effectively hampering the development of pharmacological strategies to treat the condition. Polyamines are among the substances found to decrease with age in the human brain. We found that levels of polyamines (spermidine, putrescine) decreased in aging fruit flies, concomitant with declining memory abilities. Simple spermidine feeding not only restored juvenile polyamine levels, but also suppressed age-induced memory impairment. Ornithine decarboxylase-1, the rate-limiting enzyme for de novo polyamine synthesis, also protected olfactory memories in aged flies when expressed specifically in Kenyon cells, which are crucial for olfactory memory formation. Spermidine-fed flies showed enhanced autophagy (a form of cellular self-digestion), and genetic deficits in the autophagic machinery prevented spermidine-mediated rescue of memory impairments. Our findings indicate that autophagy is critical for suppression of memory impairments by spermidine and that polyamines, which are endogenously present, are candidates for pharmacological intervention.