Histone methylation was first described more than 35 years ago, but its role has remained enigmatic. Proposed functions range from transcriptional regulation to the higher-order packaging of chromatin in preparation for mitotic condensation. Histone methylation can occur on Arg or Lys residues, with an exquisite site selectivity for Lys methylation at specific positions in the N-termini of histones H3 and H4. Thus, Lys methylation joins acetylation and phosphorylation as a third component of a 'histone code' that modifies the underlying chromatin structure of the genetic information. Notably, in contrast to acetylation and phosphorylation, Lys methylation appears to be a relatively stable histone modification, thereby providing an ideal epigenetic mark for more long-term maintenance of chromatin states. The recent discovery of the first histone Lys methyltransferase has allowed the identification of a molecular mechanism in which the specific methylation of histone H3 at Lys9 generates a binding site for heterochromatin-associated proteins. These findings have broad implications for the overall functional organization of chromosome structure at constitutive heterochromatin (e.g. centromeres) and for chromatin-dependent inheritance of gene expression patterns. This review discusses how understanding this methylation system should address some of the long-standing mysteries of heterochromatin.