The yeast histone deacetylase Rpd3 can be recruited to promoters to repress transcription initiation. Biochemical, genetic, and gene-expression analyses show that Rpd3 exists in two distinct complexes. The smaller complex, Rpd3C(S), shares Sin3 and Ume1 with Rpd3C(L) but contains the unique subunits Rco1 and Eaf3. Rpd3C(S) mutants exhibit phenotypes remarkably similar to those of Set2, a histone methyltransferase associated with elongating RNA polymerase II. Chromatin immunoprecipitation and biochemical experiments indicate that the chromodomain of Eaf3 recruits Rpd3C(S) to nucleosomes methylated by Set2 on histone H3 lysine 36, leading to deacetylation of transcribed regions. This pathway apparently acts to negatively regulate transcription because deleting the genes for Set2 or Rpd3C(S) bypasses the requirement for the positive elongation factor Bur1/Bur2.