Fragile X mental retardation protein (FMRP) and Ataxin-2 (Atx2) are triplet expansion disease- and stress granule-associated proteins implicated in neuronal translational control and microRNA function. We show that Drosophila FMRP (dFMR1) is required for long-term olfactory habituation (LTH), a phenomenon dependent on Atx2-dependent potentiation of inhibitory transmission from local interneurons (LNs) to projection neurons (PNs) in the antennal lobe. dFMR1 is also required for LTH-associated depression of odor-evoked calcium transients in PNs. Strong transdominant genetic interactions among dFMR1, atx2, the deadbox helicase me31B, and argonaute1 (ago1) mutants, as well as coimmunoprecitation of dFMR1 with Atx2, indicate that dFMR1 and Atx2 function together in a microRNA-dependent process necessary for LTH. Consistently, PN or LN knockdown of dFMR1, Atx2, Me31B, or the miRNA-pathway protein GW182 increases expression of a Ca2+/calmodulin-dependent protein kinase II (CaMKII) translational reporter. Moreover, brain immunoprecipitates of dFMR1 and Atx2 proteins include CaMKII mRNA, indicating respective physical interactions with this mRNA. Because CaMKII is necessary for LTH, these data indicate that fragile X mental retardation protein and Atx2 act via at least one common target RNA for memory-associated long-term synaptic plasticity. The observed requirement in LNs and PNs supports an emerging view that both presynaptic and postsynaptic translation are necessary for long-term synaptic plasticity. However, whereas Atx2 is necessary for the integrity of dendritic and somatic Me31B-containing particles, dFmr1 is not. Together, these data indicate that dFmr1 and Atx2 function in long-term but not short-term memory, regulating translation of at least some common presynaptic and postsynaptic target mRNAs in the same cells.