Diverse post-translational modifications of histone N-termini represent an important epigenetic mechanism for the organization of chromatin structure and the regulation of gene activity. Within the last three years, great progress has been made in understanding the functional implications of histone methylation, in particular through the characterization of histone methyltransferases (HMTases) that direct the site-specific methylation of lysine positions in the histone H3 N-terminus. Histone lysine methylation has been linked with pericentric heterochromatin formation, X-inactivation, Polycomb group (Pc-G)-dependent gene repression and epigenetic control of transcription units at euchromatic positions. Together, these regulatory roles have strongly established histone lysine methylation as a central epigenetic modification for the organization of eukaryotic chromatin. However, they also create a paradox: if histone lysine methylation is present at so many chromatin regions, how can it impart epigenetic information? We provide evidence that differences in distinct methylation states (mono- vs. di- vs. trimethylation) and selective combinations of individually methylated lysine positions can indeed index chromatin regions, resulting in epigenetic landmarks for the partitioning of eukaryotic chromatin.