Chromatin regulation relies on “writer” enzymes that add posttranslational modifications to histone proteins. Variant polycomb repressive complex 1 (PRC1) exists as several subtypes, which are “writers” of ubiquitylation on histone H2A K118 and K119, crucial for transcriptional repression during development and cell identity determination. The mechanism by which dynamic chromatin exploration by variant PRC1 complexes couples to ubiquitin writing is unknown. Here, we developed a single-molecule approach to directly observe chromatin interactions and ubiquitylation by PRC1. We find that variant PRC1 transiently samples chromatin until it reaches a catalytically competent nucleosome-bound state, resulting in E2 recruitment and ubiquitin transfer. Variant PRC1 is weakly processive in ubiquitylating neighboring nucleosomes. Moreover, activity differences between PRC1 subtypes, containing either a PCGF1 or PCGF4 subunit, result from distinct probabilities of achieving a catalytically competent state. Our results thus demonstrate that the dynamic formation of an active complex between variant PRC1, E2, and chromatin is the critical determinant of subtype-specific variant PRC1 activity.