Epigenetic differences are a common feature of many diseases, including cancer, and disease-associated changes have even been detected in bodily fluids. DNA modification studies in circulating DNA (cirDNA) may lead to the development of specific non-invasive biomarkers. To test this hypothesis, we investigated cirDNA modifications in prostate cancer patients with locally confined disease (n = 19), in patients with benign prostate hyperplasias (n = 20) and in men without any known prostate disease (n = 20). This initial discovery screen identified 39 disease-associated changes in cirDNA modification, and seven of these were validated using the sodium bisulfite-based mapping of modified cytosines in both the discovery cohort and an independent 38-patient validation cohort. In particular, we showed that the DNA modification of regions adjacent to the gene encoding ring finger protein 219 distinguished prostate cancer from benign hyperplasias with good sensitivity (61%) and specificity (71%). We also showed that repetitive sequences detected in this study were meaningful, as they indicated a highly statistically significant loss of DNA at the pericentromeric region of chromosome 10 in prostate cancer patients (p = 1.8 × 10-6). Based on these strong univariate results, we applied machine-learning techniques to develop a multi-locus biomarker that correctly distinguished prostate cancer samples from unaffected controls with 72% accuracy. Lastly, we used systems biology techniques to integrate our data with publicly available DNA modification and transcriptomic data from primary prostate tumors, thereby prioritizing genes for further studies. These data suggest that cirDNA epigenomics are promising source for non-invasive biomarkers.