Polycomb Repressive Complex (PRC) 1 and PRC2 regulate genes involved in differentiation and development. However, the mechanism for how PRC1 and PRC2 are recruited to genes in mammalian cells is unclear. Here we present evidence for an interaction between the transcription factor REST, PRC1, and PRC2 and show that RNF2 and REST co-regulate a number of neuronal genes in human teratocarcinoma cells (NT2-D1). Using NT2-D1 cells as a model of neuronal differentiation, we furthermore showed that retinoic-acid stimulation led to displacement of PRC1 at REST binding sites, reduced H3K27Me3, and increased gene expression. Genome-wide analysis of Polycomb binding in Rest-/- and Eed-/- mouse embryonic stem (mES) cells showed that Rest was required for PRC1 recruitment to a subset of Polycomb regulated neuronal genes. Furthermore, we found that PRC1 can be recruited to Rest binding sites independently of CpG islands and the H3K27Me3 mark. Surprisingly, PRC2 was frequently increased around Rest binding sites located in CpG-rich regions in the Rest-/- mES cells, indicating a more complex interplay where Rest also can limit PRC2 recruitment. Therefore, we propose that Rest has context-dependent functions for PRC1- and PRC2- recruitment, which allows this transcription factor to act both as a recruiter of Polycomb as well as a limiting factor for PRC2 recruitment at CpG islands.