The lncRNAs Airn, Kcnq1ot1, and Xist recruit Polycomb Repressive Complexes (PRCs) and repress genes over multi-megabase genomic regions, but how they interact with proteins to carry out repression remain poorly understood. To investigate, we conducted RNA-immunoprecipitations from formaldehyde-crosslinked mouse trophoblast stem cells, using antibodies against 27 proteins known to associate with Xist. Relative to other chromatin-bound transcripts, Airn, Kcnq1ot1, and Xist exhibited enriched and highly correlated associations with several RNA-binding proteins. The degree of repression induced by Airn, Kcnq1ot1, and Xist unexpectedly correlated with the extent to which the lncRNAs partitioned protein associations into communities. HNRNPU, a chromatin-associated RNA-binding protein, exhibited enriched association with, and was required to induce PRC-directed modifications by, all three lncRNAs, without being necessary for proper localization of Airn or Kcnq1ot1. Our data nominate multivalent RNA-protein interaction domains, along with the chromatin-associated RNA-binding protein HNRNPU, as features important for long-range gene regulation induced by chromatin-associated RNAs.