Cancer cells undergo epigenome deregulation causing altered DNA methylation patterns, but in the tumor microenvironment, it is unknown if defining genome-wide DNA methylation alterations also exist. Here, we used whole-genome bisulphite sequencing to show for the first time that cancer-associated fibroblasts (CAFs) from localized prostate cancer display remarkably distinct and significant changes in DNA methylation at regulatory elements, including enhancers and promoters, compared to non-malignant fibroblasts (NPFs). Differentially methylated regions (DMRs) were identified in the tumor stroma that correlate with altered expression of genes associated with cancer-related functions and these DMRs can accurately distinguish CAFs from NPFs. Notably, a subset of DMRs also common to cancer epithelial cells was identified, suggesting a common malignant epigenetic pathway. These distinct methylation changes identified in CAFs provide new epigenetic hallmarks of the cancer microenvironment and promise novel biomarkers to aid in the diagnosis and clinical management of prostate cancer.