The SUV39 class of methyltransferase enzymes deposits histone H3 lysine 9 di- and trimethylation (H3K9me2/3), the hallmark of constitutive heterochromatin. How these enzymes are regulated to mark specific genomic regions as heterochromatic is poorly understood. Clr4 is the sole H3K9me2/3 methyltransferase in the fission yeast and recent evidence suggests that ubiquitination of lysine 14 on histone H3 (H3K14ub) plays a key role in H3K9 methylation. However, the molecular mechanism of this regulation and its role in heterochromatin formation remain to be determined. Our structure-function approach shows that the H3K14ub substrate binds specifically and tightly to the catalytic domain of Clr4, and thereby stimulates the enzyme by over 250-fold. Mutations that disrupt this mechanism lead to a loss of H3K9me2/3 and abolish heterochromatin silencing similar to deletion. Comparison with mammalian SET domain proteins suggests that the Clr4 SET domain harbors a conserved sensor for H3K14ub, which mediates licensing of heterochromatin formation.