Recently we identified a new family of histone deacetylases in higher eukaryotes related to yeast HDA1 and showed their differentiation-dependent expression. Data presented here indicate that HDAC5 (previously named mHDA1), one member of this family, might be a potent regulator of cell differentiation by interacting specifically with determinant transcription factors. We found that HDAC5 was able to interact in vivo and in vitro with MEF2A, a MADS box transcription factor, and to strongly inhibit its transcriptional activity. Surprisingly, this repression was independent of HDAC5 deacetylase domain. The N-terminal non-deacetylase domain of HDAC5 was able to ensure an efficient repression of MEF2A-dependent transcription. We then mapped protein domains involved in the HDAC5-MEF2A interaction and showed that MADS box/MEF2-domain region of MEF2A interacts specifically with a limited region in the N-terminal part of HDAC5 which also possesses a distinct repressor domain. These data show that two independent class II histone deacetylases HDAC4 and HDAC5 are able to interact with members of the MEF2 transcription factor family and regulate their transcriptional activity, thus suggesting a critical role for these deacetylases in the control of cell proliferation/differentiation.