Polycomb group (PcG) proteins form multimeric chromatin-associated protein complexes that are involved in heritable repression of gene activity. Two distinct human PcG complexes have been characterized. The EED/EZH2 PcG complex utilizes histone deacetylation to repress gene activity. The HPC/HPH PcG complex contains the HPH, RING1, BMI1, and HPC proteins. Here we show that vertebrate Polycomb homologs HPC2 and XPc2, but not M33/MPc1, interact with the histone lysine methyltransferase (HMTase) SUV39H1 both in vitro and in vivo. We further find that overexpression of SUV39H1 induces selective nuclear relocalization of HPC/HPH PcG proteins but not of the EED/EZH2 PcG proteins. This SUV39H1-dependent relocalization concentrates the HPC/HPH PcG proteins to the large pericentromeric heterochromatin domains (1q12) on human chromosome 1. Within these PcG domains we observe increased H3-K9 methylation. Finally, we show that H3-K9 HMTase activity is associated with endogenous HPC2. Our findings suggest a role for the SUV39H1 HMTase and histone H3-K9 methylation in the targeting of human HPC/HPH PcG proteins to modified chromatin structures.