DNA modifications such as 5-methylcytosine (5mC) and 5-hydroxymethylcytosine (5hmC) are epigenetic marks known to affect global gene expression in mammals. Given their prevalence in the human genome, close correlation with gene expression and high chemical stability, these DNA epigenetic marks could serve as ideal biomarkers for cancer diagnosis. Taking advantage of a highly sensitive and selective chemical labeling technology, we report here the genome-wide profiling of 5hmC in circulating cell-free DNA (cfDNA) and in genomic DNA (gDNA) of paired tumor and adjacent tissues collected from a cohort of 260 patients recently diagnosed with colorectal, gastric, pancreatic, liver or thyroid cancer and normal tissues from 90 healthy individuals. 5hmC was mainly distributed in transcriptionally active regions coincident with open chromatin and permissive histone modifications. Robust cancer-associated 5hmC signatures were identified in cfDNA that were characteristic for specific cancer types. 5hmC-based biomarkers of circulating cfDNA were highly predictive of colorectal and gastric cancers and were superior to conventional biomarkers and comparable to 5hmC biomarkers from tissue biopsies. Thus, this new strategy could lead to the development of effective, minimally invasive methods for diagnosis and prognosis of cancer from the analyses of blood samples.