Circulating nucleic acids (CNAs) are under investigation as a liquid biopsy in cancer as potential non-invasive biomarkers, as stable structure in circulation nucleosomes could be valuable sources for detection of cancer-specific alterations in histone modifications. Our interest is in histone methylation marks with a focus on colorectal cancer, one of the leading cancers respective the incidence and mortality. Our previous work included the analysis of trimethylations of lysine 9 on histone 3 (H3K9me3) and of lysine 20 on histone 4 (H4K20me3) by chromatin immuno- precipitation-related PCR in circulating nucleosomes. Here we asked whether global immunologic measurement of histone marks in circulation could be a suitable approach to show their potential as biomarkers. In addition to H3K9me3 and H4K20me3 we also measured H3K27me3 in plasma samples from CRC patients (n = 63) and cancer free individuals (n = 40) by ELISA-based methylation assays. Our results show that of three marks, the amounts of H3K27me3 (p = 0.04) and H4K20me3 (p < 0.001) were significantly lower in CRC patients than in healthy controls. For H3K9me3 similar amounts were measured in both groups. Areas under the curve (AUC) in receiver operating characteristic (ROC) curves indicating the power of CRC detection were 0.620 for H3K27me3, 0.715 for H4K20me3 and 0.769 for the combination of both markers. In conclusion, findings of this preliminary study reveal the potential of blood-based detection of CRC by quantification of histone methylation marks and the additive effect of the marker combination.