The inflammatory tumor microenvironment is a fertile niche accelerating prostate cancer (PCa). We have reported that heme-oxygenase (HO-1) had a strong anti-tumoral effect in PCa. We previously undertook an in-depth proteomics study to build the HO-1 interactome in PCa. In this work, we used a bioinformatics approach to address the biological significance of HO-1 interactors. Open-access PCa datasets were mined to address the clinical significance of the HO-1 interactome in human samples. HO-1 interactors were clustered into groups according to their expression profile in PCa patients. We focused on the myxovirus resistance gene (MX1) as: (1) it was significantly upregulated under HO-1 induction; (2) it was the most consistently downregulated gene in PCa vs. normal prostate; (3) its loss was associated with decreased relapse-free survival in PCa; and (4) there was a significant positive correlation between MX1 and HMOX1 in PCa patients. Further, MX1 was upregulated in response to endoplasmic reticulum stress (ERS), and this stress triggered apoptosis and autophagy in PCa cells. Strikingly, MX1 silencing reversed ERS. Altogether, we showcase MX1 as a novel HO-1 interactor and downstream target, associated with ERS in PCa and having a high impact in the clinical setting.