In Drosophila melanogaster, the Polycomb-group (PcG) genes have been identified as repressors of gene expression. They are part of a cellular memory system that is responsible for the stable transmission of gene activity to progeny cells. PcG proteins form a large multimeric, chromatin-associated protein complex, but the identity of its components is largely unknown. Here, we identify two human proteins, HPH1 and HPH2, that are associated with the vertebrate PcG protein BMI1. HPH1 and HPH2 coimmunoprecipitate and cofractionate with each other and with BMI1. They also colocalize with BMI1 in interphase nuclei of U-2 OS human osteosarcoma and SW480 human colorectal adenocarcinoma cells. HPH1 and HPH2 have little sequence homology with each other, except in two highly conserved domains, designated homology domains I and II. They share these homology domains I and II with the Drosophila PcG protein Polyhomeotic (Ph), and we, therefore, have named the novel proteins HPH1 and HPH2. HPH1, HPH2, and BMI1 show distinct, although overlapping expression patterns in different tissues and cell lines. Two-hybrid analysis shows that homology domain II of HPH1 interacts with both homology domains I and II of HPH2. In contrast, homology domain I of HPH1 interacts only with homology domain II of HPH2, but not with homology domain I of HPH2. Furthermore, BMI1 does not interact with the individual homology domains. Instead, both intact homology domains I and II need to be present for interactions with BMI1. These data demonstrate the involvement of homology domains I and II in protein-protein interactions and indicate that HPH1 and HPH2 are able to heterodimerize.