Based on the prediction that histone lysine demethylases may contain the JmjC domain, we examined the methylation patterns of five knock-out strains (ecm5Delta, gis1Delta, rph1Delta, jhd1Delta, and jhd2Delta (yjr119cDelta)) of Saccharomyces cerevisiae. Mass spectrometry (MS) analyses of histone H3 showed increased modifications in all mutants except ecm5Delta. High-resolution MS was used to unequivocally differentiate trimethylation from acetylation in various tryptic fragments. The relative abundance of specific fragments indicated that histones K36me3 and K4me3 accumulate in rph1Delta and jhd2Delta strains, respectively, whereas both histone K36me2 and K36me accumulate in gis1Delta and jhd1Delta strains. Analyses performed with strains overexpressing the JmjC proteins yielded changes in methylation patterns that were the reverse of those obtained in the complementary knock-out strains. In vitro enzymatic assays confirmed that the JmjC domain of Rph1 specifically demethylates K36me3 primarily and K36me2 secondarily. Overexpression of RPH1 generated a growth defect in response to UV irradiation. The demethylase activity of Rph1 is responsible for the phenotype. Collectively, in addition to Jhd1, our results identified three novel JmjC domain-containing histone demethylases and their sites of action in budding yeast S. cerevisiae. Furthermore, the methodology described here will be useful for identifying histone demethylases and their target sites in other organisms.