Widespread genome hypo-methylation and promoter hyper-methylation of epithelium-specific genes are hallmarks of stable epithelial-to-mesenchymal transition (EMT), which in prostate cancer (PCa) correlates with castration resistance, cancer stem cells generation, chemoresistance and worst prognosis. Exploiting our consolidated ‘ex-vivo' system, we show that cancer-associated fibroblasts (CAFs) released factors have pivotal roles in inducing genome methylation changes required for EMT and stemness in EMT-prone PCa cells. By global DNA methylation analysis and RNA-Seq, we provide compelling evidence that conditioned media from CAFs explanted from two unrelated patients with advanced PCa, stimulates concurrent DNA hypo- and hyper-methylation required for EMT and stemness in PC3 and DU145, but not in LN-CaP and its derivative C4-2B, PCa cells. CpG island (CGI) hypermethylation associates with repression of genes required for epithelial maintenance and invasion antagonism, whereas activation of EMT markers and stemness genes correlate with CGI hypo-methylation. Remarkably, methylation variations and EMT-regulated transcripts almost completely reverse qualitatively and quantitatively during MET. Unsupervised clustering analysis of the PRAD TCGA data set with the differentially expressed (DE) and methylated EMT signature, identified a gene cluster of DE genes defined by a CAF+ and AR- phenotype and worst diagnosis. This gene cluster includes the relevant factors for EMT and stemness, which display DNA methylation variations in regulatory regions inversely correlated to their expression changes, thus strongly sustaining the ex-vivo data. DNMT3A-dependent methylation is essential for silencing epithelial maintenance and EMT counteracting genes, such as CDH1 and GRHL2, that is, the direct repressor of ZEB1, the key transcriptional factor for EMT and stemness. Accordingly, DNMT3A knock-down prevents EMT entry. These results shed light on the mechanisms of establishment and maintenance of coexisting DNA hypo- and hyper-methylation patterns during cancer progression, the generation of EMT and cell stemness in advanced PCa, and may pave the way to new therapeutic implications.