The ‘histone code’ hypothesis states that chromatin‐based regulation of nuclear processes such as transcription is brought about by the combination of distinct modifications (histone marks) at specific loci. Its correct establishment involves chromatin cross‐talks, ensuring an ordered and concerted deposition/removal of a particular set of modifications that act together to give the correct transcriptional outcome. Histone methylation on lysine residues can negatively or positively impact on gene transcription, depending on the residue and on its degree of methylation. Thanks to this complexity and given the number of chromatin ‘readers’ that can recognize methylated lysine residues, histone methylation plays a very special role in specifying the various chromatin states. The recent discovery of histone demethylases, which represent a large family of enzymes often containing histone modification binding modules, sheds new light on cross‐talk mechanisms involving methylated residues. In the present review, after a brief overview of the various families of histone demethylases, we describe the different mechanisms by which they participate in chromatin cross‐talks and how these mechanisms are integrated to achieve the mutual exclusion or the link between chromatin marks, leading to the establishment of the correct histone code.