The importance of histone methylation in gene regulation was suggested over 40 years ago. Yet, the dynamic nature of this histone modification was recognized only recently, with the discovery of the first histone demethylase nearly five years ago. Since then, our insight into the mechanisms, structures, and macromolecular complexes of these enzymes has grown exponentially. Overall, the evidence strongly supports a key role for histone demethylases in eukaryotic transcription and other chromatin-dependent processes. Here, we examine these and related facets of histone demethylases discovered to date, focusing on their biochemistry, structure, and enzymology.