Epigenetic gene silencing is one of the fundamental mechanisms for ensuring proper gene expression patterns during cellular differentiation and development. Histone deacetylases (HDACs) are evolutionally conserved enzymes that remove acetyl modifications from histones and play a central role in epigenetic gene silencing. In cells, HDAC forms a multiprotein complex (HDAC complex) in which the associated proteins are believed to help HDAC carry out its cellular functions. Though each HDAC complex contains distinct components, the presence of isoforms for some of the components expands the variety of complexes and the diversity of their cellular roles. Recent studies have also revealed a functional link between HDAC complexes and specific histone demethylases. In this paper, we summarize the distinct and cooperative roles of four class I HDAC complexes, Sin3, NuRD, CoREST, and NCoR/SMRT, with respect to their component diversity and their relationship with specific histone demethylases.