Prostate cancer (PCa) is the second leading cause of cancer death in men. Although previous studies in PCa have focused on cell adherens junctions (AJs), key players in metastasis, they have left the molecular mechanisms unexplored. Inflammation and the involvement of reactive oxygen species (ROS) are critical in the regulation of cell adhesion and the integrity of the epithelium. Heme oxygenase-1 (HO-1) counteracts oxidative and inflammatory damage. Here, we investigated whether HO-1 is implicated in the adhesive and morphological properties of tumor cells. Genes differentially regulated by HO-1 were enriched for cell motility and adhesion biological processes. HO-1 induction, increased E-cadherin and β-catenin levels. Immunofluorescence analyses showed a striking remodeling of E-cadherin/ β-catenin based AJs under HO-1 modulation. Interestingly, the enhanced levels of E-cadherin and β-catenin coincided with a markedly change in cell morphology. To further our analysis we sought to identify HO-1 binding proteins that might participate in the regulation of cell morphology. A proteomics approach identified Muskelin, as a novel HO-1 partner, strongly implicated in cell morphology regulation. These results define a novel role for HO-1 in modulating the architecture of cell-cell interactions, favoring a less aggressive phenotype and further supporting its anti-tumoral function in PCa.