Enhancer of Zeste is a Polycomb Group protein essential for the establishment and maintenance of repression of homeotic and other genes. In the early embryo it is found in a complex that includes ESC and is recruited to Polycomb Response Elements. We show that this complex contains a methyltransferase activity that methylates lysine 9 and lysine 27 of histone H3, but the activity is lost when the E(Z) SET domain is mutated. The lysine 9 position is trimethylated and this mark is closely associated with Polycomb binding sites on polytene chromosomes but is also found in centric heterochromatin, chromosome 4, and telomeric sites. Histone H3 methylated in vitro by the E(Z)/ESC complex binds specifically to Polycomb protein.