A step toward the molecular classification of prostate cancer was the discovery of recurrent erythroblast transformation-specific rearrangements, most commonly fusing the androgen-regulated TMPRSS2 promoter to ERG. The TMPRSS2-ERG fusion is observed in around 90% of tumors that overexpress the oncogene ERG. The goal of the current study was to complete the characterization of these ERG-overexpressing prostate cancers. Using fluorescence in situ hybridization and reverse transcription-polymerase chain reaction assays, we screened 101 prostate cancers, identifying 34 cases (34%) with the TMPRSS2-ERG fusion. Seven cases demonstrated ERG rearrangement by fluorescence in situ hybridization without the presence of TMPRSS2-ERG fusion messenger RNA transcripts. Screening for known 5′ partners, we determined that three cases harbored the SLC45A3-ERG fusion. To discover novel 5′ partners in these ERG-overexpressing and ERG-rearranged cases, we used paired-end RNA sequencing. We first confirmed the utility of this approach by identifying the TMPRSS2-ERG fusion in a known positive prostate cancer case and then discovered a novel fusion involving the androgen-inducible tumor suppressor, NDRG1 (N-myc downstream regulated gene 1), and ERG in two cases. Unlike TMPRSS2-ERG and SCL45A3-ERG fusions, the NDRG1-ERG fusion is predicted to encode a chimeric protein. Like TMPRSS2, SCL45A3 and NDRG1 are inducible not only by androgen but also by estrogen. This study demonstrates that most ERG-overexpressing prostate cancers harbor hormonally regulated TMPRSS2-ERG, SLC45A3-ERG, or NDRG1-ERG fusions. Broader implications of this study support the use of RNA sequencing to discover novel cancer translocations.