Contemporary challenges of prostate cancer (PCa) include overdiagnosis and overtreatment, entailing the need for novel clinical tools to improve risk stratification and therapy selection. PCa diagnosis and prognostication might be perfected using epigenetic biomarkers, among which aberrant DNA methylation of microRNA promoters has not been systematically explored. Herein, we identified aberrantly methylated microRNAs promoters in PCa and assessed its diagnostic and prognostic biomarker potential. Using HumanMethylation450 BeadChip-based analysis differentially methylated CpGs in microRNA promoters were identified. Promoter methylation of six microRNAs (miR-34b/c, miR-129-2, miR-152, miR-193b, miR-663a and miR-1258) was analyzed by qMSP in three sets (180 prostatectomies, 95 urine sediments and 74 prostate biopsies). Biomarkers' diagnostic (validity estimates) and prognostic disease-free (DFS) and disease-specific survival (DSS) performance was assessed. Significantly higher promoter methylation levels in PCa were confirmed for six candidate microRNAs. Except for miR-152, all displayed AUC values higher than 0.90, with miR-1258 and miR-193b disclosing the best performance (AUC = 0.99 and AUC = 0.96, respectively). In urine samples, miR-193b showed the best performance (91.6% sensitivity, 95.7% specificity, AUC = 0.96). Moreover, higher miR-129-2 independently predicted for shorter DSS and miR-34b/c methylation levels independently predicted for shorter DFS and DSS. Quantitative miR-193b, miR-129-2 and miR-34b/c promoter methylation might be clinically useful PCa biomarkers for non-invasive detection/diagnosis and prognostication, both in tissue and urine samples.