SET domain methyltransferases deposit methyl marks on specific histone tail lysine residues and play a major role in epigenetic regulation of gene transcription. We solved the structures of the catalytic domains of GLP, G9a, Suv39H2 and PRDM2, four of the eight known human H3K9 methyltransferases in their apo conformation or in complex with the methyl donating cofactor, and peptide substrates. We analyzed the structural determinants for methylation state specificity, and designed a G9a mutant able to tri-methylate H3K9. We show that the I-SET domain acts as a rigid docking platform, while induced-fit of the Post-SET domain is necessary to achieve a catalytically competent conformation. We also propose a model where long-range electrostatics bring enzyme and histone substrate together, while the presence of an arginine upstream of the target lysine is critical for binding and specificity.