Epigenetic modifications include dynamic chemical alterations on specific DNA bases that do not involve changes in the DNA sequence. In particular, 5-hydroxymethylcytosine (5-hmC) is a tissue-type specific epigenetic modification on the base cytosine. Reduction in 5-hmC levels has been recently associated with various types of cancers, such as leukemia, indicating its potential as a biomarker for early disease diagnosis. LC-MS/MS is the most reliable technique for 5-hmC detection. However, detecting 5-hmC levels is extremely challenging, especially in blood which contains very low 5hmC content, due to its low ionization efficiency and interference from other nucleobases. Here we introduce a simple enzymatic procedure for selective labeling of 5-hmC with a molecule of high ionization efficiency, resulting in eight folds increase in the LC-MS/MS response to 5-hmC. The limit of quantification (LOQ) of our technique is 0.001% 5-hmC per total nucleotides (below physiologically relevant levels), using only 500 ng DNA per measurement. We demonstrate that we can quantitatively differentiate between 5-hmC levels in healthy and leukemia blood samples, using just 200 ng DNA per measurement. Thus, our method may open a new era of mass spectroscopy-based diagnostics for early detection of diseases associated with extremely reduced 5-hmC levels, such as leukemia.