Recurrent gene fusions and chromosomal rearrangements were previously thought to be the primary oncogenic mechanism of hematological malignancies and sarcomas. The recent discovery of recurrent gene fusions in a majority of prostate cancers represents a paradigm shift in understanding the molecular mechanisms of one of the most prevalent epithelial malignancies, with important clinical and biologic implications. The prostate cancer gene fusions that have been identified so far are characterized by 5′-genomic regulatory elements, most notably the androgen-controlled prostate specific gene, transmembrane protease serine 2, fused to members of the erythroblastosis virus E26 transforming sequence family of transcription factors, most notably ERG, leading to the overexpression of oncogenic transcription factors. The erythroblastosis virus E26 transforming sequence gene fusions most likely define a distinct class of prostate cancer with potential implications for early diagnosis, prognosis, and rational therapeutic targeting. In this review, we summarize the bioinformatics approach that led to the discovery of gene fusions, the current state of the frequency, and diversity of gene fusions that define the molecular heterogeneity of prostate cancer, their associations with prostate cancer progression and clinical outcome, the subsequent morphological characteristics, and the potential application of gene fusions as biomarkers in the diagnosis and management of prostate cancer.