The evolutionarily conserved Elongator Complex associates with RNA polymerase II for transcriptional elongation. Elp3 is the catalytic subunit, contains histone acetyltransferase activity, and is associated with neurodegeneration in humans. Elp1 is a scaffolding subunit and when mutated causes familial dysautonomia. Here, we show that "elp3" and "elp1" are required for aversive long-term olfactory memory in "Drosophila." RNAi knockdown of "elp3" in adult mushroom bodies impairs long-term memory (LTM) without affecting earlier forms of memory. RNAi knockdown with coexpression of "elp3" cDNA reverses the impairment. Similarly, RNAi knockdown of "elp1" impairs LTM and coexpression of "elp1" cDNA reverses this phenotype. The LTM deficit in "elp3" and "elp1" knockdown flies is accompanied by the abolishment of a LTM trace, which is registered as increased calcium influx in response to the CS+ odor in the a-branch of mushroom body neurons. Coexpression of "elp1" or "elp3" cDNA rescues the memory trace in parallel with LTM. These data show that the Elongator complex is required in adult mushroom body neurons for long-term behavioral memory and the associated long-term memory trace.