Histone methylation is a key element of the eukaryotic epigenome. Since the discovery of the first histone demethylase (HDM) in 2004, more than 20 demethylases have been identified and characterized. They belong to either the LSD family or the JmjC family, demonstrating the reversibility of all methylation states at almost all major histone lysine methylation sites. These findings ended decades of debate about the reversibility of histone methylation, representing a major breakthrough that shifts our understanding of epigenetic inheritance and regulation of genome function. Here, we summarize the discovery of HDMs and more recent advances, challenges, and future prospects of HDM research.