Noncoding RNAs (ncRNAs) are emerging as key molecules in human cancer, with the potential to serve as novel markers of disease and to reveal uncharacterized aspects of tumor biology. Here we discover 121 unannotated prostate cancer-associated ncRNA transcripts (PCATs) by ab initio assembly of high-throughput sequencing of polyA(+) RNA (RNA-Seq) from a cohort of 102 prostate tissues and cells lines. We characterized one ncRNA, PCAT-1, as a prostate-specific regulator of cell proliferation and show that it is a target of the Polycomb Repressive Complex 2 (PRC2). We further found that patterns of PCAT-1 and PRC2 expression stratified patient tissues into molecular subtypes distinguished by expression signatures of PCAT-1-repressed target genes. Taken together, our findings suggest that PCAT-1 is a transcriptional repressor implicated in a subset of prostate cancer patients. These findings establish the utility of RNA-Seq to identify disease-associated ncRNAs that may improve the stratification of cancer subtypes.