Extensive neurogenetic analysis has shown that memory formation depends critically on cAMP-protein kinase A (PKA) signaling. Details of how this pathway is involved in memory formation, however, remain to be fully elucidated. From a large-scale behavioral screen in Drosophila, we identified the yu mutant to be defective in one-day memory after spaced training. The yu mutation disrupts a gene encoding an A-kinase anchoring protein (AKAP). AKAPs comprise a family of proteins, which determine the subcellular localization of PKAs and thereby critically restrict cAMP signaling within a cell. Further behavioral characterizations revealed that long-term memory (LTM) was disrupted specifically in the yu mutant, whereas learning, short-term memory and anesthesia-resistant memory all appeared normal. Another independently isolated mutation of the yu gene failed to complement the LTM defect associated with the yu mutation, and this phenotypic defect could be rescued by induced acute expression of a yu(+) transgene, suggesting that yu functions physiologically during memory formation. AKAP Yu is expressed preferentially in the mushroom body (MB) neuroanatomical structure, and expression of a yu(+) transgene to the MB, but not to other brain regions, is sufficient to rescue the LTM defect of the yu mutant. These observations lead us to conclude that proper localization of PKA by Yu AKAP in MB neurons is required for the formation of LTM.