Histone methylation is a reversible modification regulated by the antagonistic functions of residue-specific histone methyltransferases and demethylases. Although methylation of histone H3 at lysines 4 and 36 is linked to transcription, the roles of histone demethylases in transcription regulation are not understood. Here we show that overexpression of either Jhd1 or Rph1, two JmjC-domain proteins, bypasses the requirement for the positive elongation factor gene BUR1. Biochemical analysis and chromatin immunoprecipitation experiments indicate that Rph1 functions as a specific demethylase for H3 K36me3 and K36me2, directly regulating Lys(36) methylation in transcribed regions. Both Jhd1 and Rph1 are required for normal levels of RNA polymerase II cross-linking to genes. Taken together, these findings indicate that a general function of histone demethylases for H3 Lys(36) is to promote transcription elongation by antagonizing repressive Lys(36) methylation by Set2.