Loss of the putative tumor suppressor BAP1 is a candidate biomarker for adverse prognosis in many cancer types, but conversely for improved survival in others. Studies on the expression and prognostic role of BAP1 in prostate cancer are currently lacking. We used a tissue microarray of 17,747 individual prostate cancer samples linked with comprehensive pathological, clinical and molecular data and studied the immunohistochemical expression of BAP1. BAP1 expression was typically up regulated in cancers as compared to adjacent normal prostatic glands. In 15,857 cancers, BAP1 staining was weak in 3.3%, moderate in 41.6% and strong in 17.4%. Strong BAP1 staining was associated with advanced tumor stage (p<0.0001), high classical and quantitative Gleason grade (p<0.0001), lymph node metastasis (p<0.0001), a positive surgical margin (p=0.0019) and early biochemical recurrence (p<0.0001). BAP1 expression was linked to ERG-fusion type cancers, with strong BAP1 staining in 12% of ERG-negative, but 30% of ERG-positive cancers (p<0.0001). Subset analyses in 5,415 cancers with and 4,217 cancers without TMPRSS2:ERG fusion revealed that these associations with tumor phenotype and patient outcome were largely driven by the subset of ERG-negative tumors. Multivariate analysis revealed that the prognostic impact was independent of established prognostic features in ERG negative p<0.001) but not in ERG positive cancers. BAP1 expression was further linked to androgen receptor (AR) expression: Only 2% of AR-negative, but 33% of strongly AR expressing cancers had strong BAP1 expression (p<0.0001). In conclusion, this study shows that BAP1 up regulation is linked to prostate cancer progression and aggressiveness.