Prostate cancer (PCa) cells display abnormal expression of proteins resulting in an augmented capacity to resist chemotherapy and colonize distant organs. We have previously shown the anti-tumoral role of heme oxygenase 1 (HO-1) in this disease. In this work, we undertook a mass spectrometry-based proteomics study to identify HO-1 molecular interactors that might collaborate with its modulatory function in PCa. Among the HO-1 interactors, we identified proteins with nuclear localization. Correlation analyses, using the PCa GSE70770 dataset, showed a significant and positive correlation between HMOX1 and 6 of those genes. Alternatively, HMOX1 and YWHAZ showed a negative correlation. Univariable analyses evidenced that high expression of HNRNPA2B1, HSPB1, NPM1, DDB1, HMGA1, ZC3HAV1, and HMOX1 was associated with increased relapse-free survival (RFS) in PCa patients. Further, PCa patients with high HSPB1/HMOX1, DDB1/HMOX1, and YWHAZ/HMOX1 showed a worse RFS compared with patients with lower ratios. Moreover, a decrease in RFS for patients with higher scores of this signature was observed using a prognostic risk score model. However, the only factor significantly associated with a higher risk of relapse was high YWHAZ. Multivariable analyses confirmed HSPB1, DDB1, and YWHAZ independence from PCa clinic-pathological parameters. In parallel, co-immunoprecipitation analysis in PCa cells ascertained HO-1/14-3-3ζ/δ (protein encoded by YWHAZ) interaction. Herein, we describe a novel protein interaction between HO-1 and 14-3-3ζ/δ in PCa and highlight these factors as potential therapeutic targets.