Covalent modification of histones has an important role in regulating chromatin dynamics and transcription. Whereas most covalent histone modifications are reversible, until recently it was unknown whether methyl groups could be actively removed from histones. Using a biochemical assay coupled with chromatography, we have purified a novel JmjC domain-containing protein, JHDM1 (JmjC domain-containing histone demethylase 1), that specifically demethylates histone H3 at lysine 36 (H3-K36). In the presence of Fe(ii) and α-ketoglutarate, JHDM1 demethylates H3-methyl-K36 and generates formaldehyde and succinate. Overexpression of JHDM1 reduced the level of dimethyl-H3-K36 (H3K36me2) in vivo. The demethylase activity of the JmjC domain-containing proteins is conserved, as a JHDM1 homologue in Saccharomyces cerevisiae also has H3-K36 demethylase activity. Thus, we identify the JmjC domain as a novel demethylase signature motif and uncover a protein demethylation mechanism that is conserved from yeast to human.