Histone modifications are thought to regulate chromatin structure, transcription and other nuclear processes. Histone methylation was originally believed to be an irreversible modification that could only be removed by histone eviction or by dilution during DNA replication. However, the isolation of two families of enzymes that can demethylate histones has changed this notion. The biochemical activities of these histone demethylases towards specific Lys residues on histones, and in some cases non-histone substrates, have highlighted their importance in developmental control, cell-fate decisions and disease. Their ability to be regulated through protein-targeting complexes and post-translational modifications is also beginning to shed light on how they provide dynamic control during transcription.