A growing body of research indicates that pharmacological inhibition of histone deacetylases (HDACs) correlates with enhancement of long-term memory and current research is concentrated on determining the roles that individual HDACs play in cognitive function. Here, we investigate the role of HDAC4 in long-term memory formation in Drosophila. We show that overexpression of HDAC4 in the adult mushroom body, an important structure for memory formation, resulted in a specific impairment in long-term courtship memory, but had no affect on short-term memory. Overexpression of an HDAC4 catalytic mutant also abolished LTM, suggesting a mode of action independent of catalytic activity. We found that overexpression of HDAC4 resulted in a redistribution of the transcription factor MEF2 from a relatively uniform distribution through the nucleus into punctate nuclear bodies, where it colocalized with HDAC4. As MEF2 has also been implicated in regulation of long-term memory, these data suggest that the repressive effects of HDAC4 on long-term memory may be through interaction with MEF2. In the same genetic background, we also found that RNAi-mediated knockdown of HDAC4 impairs long-term memory, therefore we demonstrate that HDAC4 is not only a repressor of long-term memory, but also modulates normal memory formation.