Cancer is traditionally viewed as a primarily genetic disorder. However, it is now increasingly apparent that epigenetic abnormalities play a fundamental role in cancer development. Aberrant expression of histone-modifying enzymes has been implicated in the course of tumor initiation and progression. The discovery of a large number of histone demethylases suggests an important role for dynamic regulation of histone methylation in biological processes. The observation that overexpression, amplification or mutations of several histone demethylases have been found in many types of tumors, raise the possibility of using these enzymes as diagnostic tools as well as pave a way for the discovery of novel therapeutic targets and treatment modalities. Here, we review the current knowledge of the potential role of H3K4, H3K9 and H3K27 histone demethylases in tumorigenesis.