Polycomb-group (PcG) proteins form multimeric protein complexes, which are involved in maintaining the transcriptional repressive state of genes over successive cell generations. Components of PcG complexes and their mutual interactions have been identified and analysed through extensive genetic and biochemical analyses. Molecular mechanisms underlying PcG-mediated repression of gene activity, however, have remained largely unknown. Previously we reported the existence of two distinct human PcG protein complexes. The EED/EZH protein complex contains the embryonic ectoderm development (EED) and enhancer of zeste 2 (EZH2; refs 9,10) PcG proteins. The HPC/HPH PcG complex contains the human polycomb 2 (HPC2; ref. 11), human polyhomeotic (HPH), BMI1 (ref. 13 ) and RING1 (refs 14, 15) proteins. Here we show that EED (refs 4, 5, 6, 7, 8) interacts, both in vitro and in vivo, with histone deacetylase (HDAC) proteins. This interaction is highly specific because the HDAC proteins do not interact with other vertebrate PcG proteins. We further find that histone deacetylation activity co-immunoprecipitates with the EED protein. Finally, the histone deacetylase inhibitor trichostatin A (ref. 17) relieves transcriptional repression mediated by EED, but not by HPC2, a human homologue of polycomb. Our data indicate that PcG-mediated repression of gene activity involves histone deacetylation. This mechanistic link between two distinct, global gene repression systems is accomplished through the interaction of HDAC proteins with a particular PcG protein, EED.