DNA methylation plays an important role in carcinogenesis and is being recognized as a promising diagnostic and prognostic biomarker for a variety of malignancies including Prostate cancer (PCa). The human kallikrein-related peptidases (KLKs) have emerged as an important family of cancer biomarkers, with KLK3, encoding for Prostate Specific Antigen, being most recognized. However, few studies have examined the epigenetic regulation of KLKs and its implications to PCa. To assess the biological effect of DNA methylation on KLK6 and KLK10 expression, we treated PC3 and 22RV1 PCa cells with a demethylating drug, 5-aza-2'deoxycytidine, and observed increased expression of both KLKs, establishing that DNA methylation plays a role in regulating gene expression. Subsequently, we have quantified KLK6 and KLK10 DNA methylation levels in two independent cohorts of PCa patients operated by radical prostatectomy between 2007-2011 (Cohort I, n = 150) and 1998-2001 (Cohort II, n = 124). In Cohort I, DNA methylation levels of both KLKs were significantly higher in cancerous tissue vs. normal. Further, we evaluated the relationship between DNA methylation and clinicopathological parameters. KLK6 DNA methylation was significantly associated with pathological stage only in Cohort I while KLK10 DNA methylation was significantly associated with pathological stage in both cohorts. In Cohort II, low KLK10 DNA methylation was associated with biochemical recurrence in univariate and multivariate analyses. A similar trend for KLK6 DNA methylation was observed. The results suggest that KLK6 and KLK10 DNA methylation distinguishes organ confined from locally invasive PCa and may have prognostic value.