Recent studies have shown that PRC1-like Polycomb repressor complexes monoubiquity-late chromatin on histone H2A at lysine residue 119. Here we have analyzed the function of the polycomb protein Mel-18. Using affinity-tagged human MEL-18, we identify a polycomb-like complex, melPRC1, containing the core PRC1 proteins, RING1/2, HPH2, and CBX8. We show that, in ES cells, melPRC1 can functionally substitute for other PRC1-like complexes in Hox gene repression. A reconstituted subcomplex containing only Ring1B and Mel-18 functions as an efficient ubiquitin E3 ligase. This complex ubiquitylates free histone substrates nonspecifically but is highly specific for histone H2A lysine 119 in the context of nucleosomes. Mutational analysis demonstrates that while Ring1B is required for E3 function, Mel-18 directs this activity to H2A lysine 119 in chromatin. Moreover, this substrate-targeting function of Mel-18 is dependent on its prior phosphorylation at multiple residues, providing a direct link between chromatin modification and cell signaling pathways.