Class II histone deacetylases (HDACs) contain unique amino-terminal extensions that mediate interactions with members of the myocyte enhancer factor-2 (MEF2) family of transcription factors and responsiveness to kinases, including Ca2+/calmodulin-dependent kinase (CaMK). Despite intense investigation of class II HDACs, little is known of MEF2-independent mechanisms for transcriptional repression by these chromatin-modifying enzymes. Here, we demonstrate that class II HDACs 4 and 5 physically associate with ankyrin-repeat proteins ANKRA2 and RFXANK (RFX-B/Tvl-1/ANKRA1). ANKRA2 is a megalin- and BKCa potassium channel-interacting factor, whereas RFXANK is a positive regulator of major histocompatibility complex II (MHC II) gene expression. HDAC4 and HDAC5 interact with the ankyrin repeats of ANKRA2 and RFXANK and, through association with RFXANK, repress MHC II promoter activation. HDACs 4 and 5 also repress endogenous HLA-DRA gene expression induced by CIITA. Phosphorylation of class II HDACs by CaMK results in CRM1-dependent nuclear export of HDAC/RFXANK complexes. These results define a novel transcriptional pathway under the control of class II HDACs and suggest a role for these transcriptional repressors as signal-responsive regulators of antigen presentation.