Members of the Mad family of bHLH-Zip proteins heterodimerize with Max to repress transcription in a sequence-specific manner. Transcriptional repression by Mad:Max heterodimers is mediated by ternary complex formation with either of the corepressors mSin3A or mSin3B. We report here that mSin3A is an in vivo component of large, heterogeneous multiprotein complexes and is tightly and specifically associated with at least seven polypeptides. Two of the mSin3A-associated proteins, p50 and p55, are highly related to the histone deacetylase HDAC1. The mSin3A immunocomplexes possess histone deacetylase activity that is sensitive to the specific deacetylase inhibitor trapoxin. mSin3A-targeted repression of a reporter gene is reduced by trapoxin treatment, suggesting that histone deacetylation mediates transcriptional repression through Mad-Max-mSin3A multimeric complexes.