In eukaryotes, histone methylation is an epigenetic mechanism associated with a variety of functions related to gene regulation or genomic stability. Recently analyzed H3K9 methyltransferases (HMTases) as SUV39H1, Clr4p, DIM-5, Su(var)3-9 or SUVH2 are responsible for the establishment of histone H3 lysine 9 methylation (H3K9me), which is intimately connected with heterochromatinization. In this review, available data will be evaluated concerning (1) the phylogenetic distribution of H3K9me as heterochromatin-specific histone modification and its evolutionary stability in relation to other epigenetic marks, (2) known families of H3K9 methyltransferases, (3) their responsibility for the formation of constitutive heterochromatin and (4) the evolution of Su(var)3-9-like and SUVH-like H3K9 methyltransferases. Compilation and parsimony analysis reveal that histone H3K9 methylation is, next to histone deacetylation, the evolutionary most stable heterochromatic mark, which is established by at least two subfamilies of specialized heterochromatic HMTases in almost all studied eukaryotes.