Recent studies identified unexpected expression and transcriptional complexity of the hemoprotein myoglobin (MB) in human breast cancer but its role in prostate cancer is still unclear. Expression of MB was immunohistochemically analyzed in three independent cohorts of radical prostatectomy specimens (n = 409, n = 625, and n = 237). MB expression data were correlated with clinicopathological parameters and molecular parameters of androgen and hypoxia signaling. Expression levels of novel tumor-associated MB transcript variants and the VEGF gene as a hypoxia marker were analyzed using qRT-PCR. Fifty-three percent of the prostate cancer cases were MB positive and significantly correlated with androgen receptor (AR) expression (p < 0.001). The positive correlation with CAIX (p < 0.001) and FASN (p = 0.008) as well as the paralleled increased expression of the tumor-associated MB transcript variants and VEGF suggest that hypoxia participates in MB expression regulation. Analogous to breast cancer, MB expression in prostate cancer is associated with steroid hormone signaling and markers of hypoxia. Further studies must elucidate the novel functional roles of MB in human carcinomas, which probably extend beyond its classic intramuscular function in oxygen storage.