Polycomb proteins play essential roles in stem cell renewal and human disease. Recent studies of HOX genes and X inactivation have provided evidence for RNA cofactors in Polycomb repressive complex 2 (PRC2). Here we develop a RIP-seq method to capture the PRC2 transcriptome and identify a genome-wide pool of >9000 PRC2-interacting RNAs in embryonic stem cells. The transcriptome includes antisense, intergenic, and promoter-associated transcripts, as well as many unannotated RNAs. A large number of transcripts occur within imprinted regions, oncogene and tumor suppressor loci, and stem cell-related bivalent domains. We provide evidence for direct RNA-protein interactions, most likely via the Ezh2 subunit. We also identify Gtl2 RNA as a PRC2 cofactor that directs PRC2 to the reciprocally imprinted Dlk1 coding gene. Thus, Polycomb proteins interact with a genome-wide family of RNAs, some of which may be used as biomarkers and therapeutic targets for human disease.