HDAC4 is a potent memory repressor with overexpression of wild type or a nuclear-restricted mutant resulting in memory deficits. Interestingly, reduction of HDAC4 also impairs memory via an as yet unknown mechanism. Although histone deacetylase family members are important mediators of epigenetic mechanisms in neurons, HDAC4 is predominantly cytoplasmic in the brain and there is increasing evidence for interactions with nonhistone proteins, suggesting HDAC4 has roles beyond transcriptional regulation. To that end, we performed a genetic interaction screen in Drosophila and identified 26 genes that interacted with HDAC4, including Ubc9, the sole SUMO E2-conjugating enzyme. RNA interference-induced reduction of Ubc9 in the adult brain impaired long-term memory in the courtship suppression assay, a Drosophila model of associative memory. We also demonstrate that HDAC4 and Ubc9 interact genetically during memory formation, opening new avenues for investigating the mechanisms through which HDAC4 regulates memory formation and other neurological processes.