DNA methylation at gene promoters is considered to be associated with transcriptional repression. However, lack of a clear picture of where promoter methylation is most important has obscured our understanding of this relationship. Promoter definitions being used in different DNA methylation studies vary substantially in both their length and location relative to the transcription start site (TSS) leading to inconsistencies. We have developed Methodical, a computational method that combines RNA-seq and Whole Genome Bisulfite Sequencing (WGBS) data to identify genomic regions where DNA methylation tends to be highly correlated with nearby TSS activity, which we refer to as TSS-proximal methylation-controlled regulatory sites (TMRs). We map TMRs in prostate normal, primary tumor and metastases methylomes. We reveal that, in contrast with the conventional idea that DNA methylation silences transcription, a substantial proportion of regulatory sites display positive methylation-transcription correlations - even upstream of the TSS. We also show that the region just downstream of the TSS is the most common location of TMRs and that negative and positive TMRs are enriched for different transcription factor binding sites, genomic features and chromatin states. Ultimately, we describe how TMRs change through prostate tumor evolution.