Calcium/calmodulin-dependent protein kinase II (CaMKII) phosphorylates histone deacetylase 4 (HDAC4), a class IIa HDAC, resulting in the cytosolic accumulation of HDAC4 and the derepression of the transcription factor myocyte enhancer factor 2. Phosphorylation by CaMKII requires docking of the kinase to a specific domain of HDAC4 not present in other HDACs. Paradoxically, however, CaMKII signaling can also promote the nuclear export of other class IIa HDACs, such as HDAC5. Here, we show that HDAC4 and HDAC5 form homo- and hetero-oligomers via a conserved coiled-coil domain near their amino termini. Whereas HDAC5 alone is unresponsive to CaMKII, it becomes responsive to CaMKII in the presence of HDAC4. The acquisition of CaMKII responsiveness by HDAC5 is mediated by HDAC5's direct association with HDAC4 and can occur by phosphorylation of HDAC4 or by transphosphorylation by CaMKII bound to HDAC4. Thus, HDAC4 integrates upstream Ca(2+)-dependent signals via its association with CaMKII and transmits these signals to HDAC5 by protein-protein interactions. We conclude that HDAC4 represents a point of convergence for CaMKII signaling to downstream HDAC-regulated genes, and we suggest that modulation of the interaction of CaMKII and HDAC4 represents a means of regulating CaMKII-dependent gene programs.