Histone lysine methylation marks are epigenetic regulators that have important functions in controlling cell-specific identity. Distinct combinations of lysine methylation marks, all of which make up the chromatin signature of a particular cell type index the network system that controls which genes are activated and which are kept repressed. For a long time this type of marking by histone lysine methylation was thought to be robust and irreversible and that it is required for long term inheritance or locking a cell into its specific epigenotype. However in recent years, with the discovery of lysine specific demethylases, particularly the jmjC domain containing proteins, that target the tri-methylated lysines, it has not only been demonstrated that these marks are dynamic, but also revealed a whole new set of regulators of epigenetic plasticity. In this review we discuss the different histone lysine demethylases, their targets, biological function and potential role in cellular reprogramming and pluripotency.