Eighteen human histone deacetylases (HDACs) have been identified, and according to their sequence similarity to yeast homologs, these enzymes are grouped into distinct classes. Within class II, HDAC4, HDAC5, HDAC7, and HDAC9 share similar domain organization both within the N-terminal extension and the C-terminal catalytic domain, thus forming a subclass known as class IIa. These HDACs function as signal-responsive transcriptional corepressors. To gain further insight into their function and regulation, we utilized an N-terminal fragment of HDAC4 as bait in yeast two-hybrid screens, which uncovered myocyte enhancer factor 2C, 14-3-3zeta, and ankyrin repeat family A protein (ANKRA). ANKRA is a poorly characterized protein with an ankyrin repeat domain similar to RFXANK, a subunit of the trimeric transcription factor RFX. Mutations on genes of the RFX subunits and the coactivator CIITA are responsible for the bare lymphocyte syndrome, an immunodeficiency disorder attributed to the lack of major histocompatibility complex class II (MHCII) antigens. Through its ankyrin repeat domain, RFXANK interacted with HDAC4. Two RFXANK-binding sites were found on HDAC4 with one located within residues 118-279 and another within residues 448-666. Interestingly, this deacetylase also interacted with CIITA. Consistent with the physical interaction with RFXANK and CIITA, HDAC4 and homologs repressed MHCII expression. These results identify ANKRA, RFXANK, and CIITA as novel targets of class IIa HDACs and suggest that these deacetylases play a role in regulating MHCII expression.