Histone deacetylases (HDACs) play a pivotal role in eukaryotic gene expression by modulating the levels of acetylation of chromatin and related transcription factors. In contrast to class I HDACs (HDAC1, -2, -3 and -8), the class IIa HDACs (HDAC4, -5, -7 and -9) harbor cryptic deacetylases activity and recruit the SMRT-HDAC3 complex to repress target genes in vivo. In this regard, the specific interaction between the HDAC domain of class IIa HDACs and the C-terminal region of SMRT repression domain 3 (SRD3c) is known to be critical, but the molecular basis of this interaction has not yet been addressed. Here, we used an extensive mutant screening system, named the "partitioned one- plus two-hybrid system", to isolate SRD3c interaction-defective (SRID) mutants over the entire catalytic domains of HDAC4 (HDAC4c) and -5. The surface presentation of the SRID mutations on the HDAC4c structure revealed that most of the mutations were mapped to the rim surface of the catalytic entry site, strongly suggesting this mutational hot-spot region as the major binding surface of SRD3c. Notably, among the HDAC4c surface residues required for SRD3c binding, some residues (C667, C669, C751, D759, T760 and F871) are present only in class IIa HDACs, providing the molecular basis for the specific interactions between SRD3c and class IIa enzymes. To investigate the functional consequence of SRID mutation, the in vitro HDAC activities of HDAC4 mutants immuno-purified from HEK293 cells were measured. The levels of HDAC activity of the HDAC4c mutants were substantially decreased compared to wild-type. Consistent with this, SRID mutations of HDAC4c prevented the association of HDAC4c with the SMRT-HDAC3 complex in vivo. Our findings may provide structural insight into the binding interface of HDAC4 and -5 with SRD3c, as a novel target to design modulators specific to these enzymes.