Histone deacetylases (HDACs) have been extensively studied as drug targets in neurodegenerative diseases, but less is known about their role in healthy neurons. We tested zinc-dependent HDACs using RNAi in Drosophila melanogaster and found memory deficits with RPD3 and HDAC6. We demonstrate that HDAC6 is required in both the larval and adult stages for normal olfactory memory retention. Neuronal expression of HDAC6 rescued memory deficits, and we demonstrate that the N-terminal deacetylase (DAC) domain is required for this ability. This suggests that deacetylation of synaptic targets associated with the first DAC domain, such as the active-zone scaffold Bruchpilot, is required for memory retention. Finally, electrophysiological experiments at the neuromuscular junction reveal that HDAC6 mutants exhibit a partial block of homeostatic plasticity, suggesting that HDAC6 may be required for the stabilization of synaptic strength. The learning deficit we observe in HDAC6 mutants could be a behavioral consequence of these synaptic defects.