The study of histone lysine demethylases has become very hot recently. Many histone demethylases have been reported by different research groups with various techniques. However, how many histone lysine-methylation states can be removed by one specific demethylase and how many demethylases can remove one specific histone lysine-methylation state? It remains a daunting challenge to answer these questions to date. An in-depth discussion on recent results, three important points were provided: (1) Some demethylases can remove more histone lysine-methylation states; (2) Some prokaryotes might be endowed with histone lysine demethylases although they are devoid of histones; (3) Protein-protein interaction provides a valuable framework for a better understanding of the functions of the histone lysine demethylases. All of these will be beneficial to a better understanding of demethylases and suggest how future research can be improved.