The growth and progression of solid tumors involves dynamic cross-talk between cancer epithelium and the surrounding microenvironment. To date, molecular profiling has largely been restricted to the epithelial component of tumors; therefore, features underpinning the persistent protumorigenic phenotype of the tumor microenvironment are unknown. Using whole-genome bisulfite sequencing, we show for the first time that cancer-associated fibroblasts (CAFs) from localized prostate cancer display remarkably distinct and enduring genome-wide changes in DNA methylation, significantly at enhancers and promoters, compared to nonmalignant prostate fibroblasts (NPFs). Differentially methylated regions associated with changes in gene expression have cancer-related functions and accurately distinguish CAFs from NPFs. Remarkably, a subset of changes is shared with prostate cancer epithelial cells, revealing the new concept of tumor-specific epigenome modifications in the tumor and its microenvironment. The distinct methylome of CAFs provides a novel epigenetic hallmark of the cancer microenvironment and promises new biomarkers to improve interpretation of diagnostic samples.