Lysine methylation plays a central role in the "histone code" that regulates chromatin structure, impacts transcription, and responds to DNA damage. A single lysine can be mono-, di-, tri-methylated, or unmethylated, with different functional consequences for each of the four forms. This review (written in the early 2006) described structural aspects of methylation of histone lysine residues by two enzyme families with entirely different structural scaffolding (the SET proteins and Dot1p), and the protein motifs that recognize (decode) these methyl-lysine signals. We also discuss the recently discovered protein lysine demethylating enzymes (LSD1 and JmjC domains).