Polycomb group (PcG) proteins maintain transcriptional repression during development, likely by creating repressive chromatin states. The Extra Sex Combs (ESC) and Enhancer of Zeste [E(Z)] proteins are partners in an essential PcG complex, but its full composition and biochemical activities are not known. A SET domain in E(Z) suggests this complex might methylate histones. We purified an ESC-E(Z) complex from Drosophila embryos and found four major subunits: ESC, E(Z), NURF-55, and the PcG repressor, SU(Z)12. A recombinant complex reconstituted from these four subunits methylates lysine-27 of histone H3. Mutations in the E(Z) SET domain disrupt methyltransferase activity in vitro and HOX gene repression in vivo. These results identify E(Z) as a PcG protein with enzymatic activity and implicate histone methylation in PcG-mediated silencing.