Eukaryotic chromatin can be highly dynamic and can continuously exchange between an open transcriptionally active conformation and a compacted silenced one. Post-translational modifications of histones have a pivotal role in regulating chromatin states, thus influencing all chromatin dependent processes. Methylation is currently one of the best characterized histone modification and occurs on arginine and lysine residues. Histone methylation can regulate other modifications (e.g. acetylation, phosphorylation and ubiquitination) in order to define a precise functional chromatin environment. In this review we focus on histone methylation and demethylation, as well as on the enzymes responsible for setting these marks. In particular we are describing novel concepts on the interdependence of histone modifications marks and discussing the molecular mechanisms governing this cross-talks.