Modified histone tails in nucleosomes circulating in the blood bear the potential as cancer biomarkers. Recently, using chromatin immunopecipitation (ChIP)-related quantitative PCR, we described reduced plasma levels of the two pericentric heterochromatin-specific histone methylation marks H3K9me3 and H4K20me3 in patients with colorectal cancer (CRC). Here, by utilizing ChIP-related high-throughput sequencing, we further characterized these modifications in circulation. Plasma DNA from nucleosomes immunoprecipitated by H3K9me3- and H4K20me3-specific antibodies from patients with CRC (N = 15) and healthy subjects (N = 15) was subjected to the Roche 454 FLX sequencing, and the generated array of ChIP-enriched sequences were compared to the human reference genome. The total number of nucleosomes, of sequence reads and of diverse DNA repetitive elements were statistically compared between the study groups. Total nucleosome amount was not different in both groups. Concerning both histone modifications, lower numbers of sequence reads were detected in CRC patients as compared with healthy controls (medians in H3K9me3: 32 vs. 61; p < 0.01; in H4K20me3: 54 vs. 88; p < 0.01). Size of fragments was not different in both groups. Most abundant sequences were repetitive LINE and SINE elements while simple repeats, LTR, DNA, SAT, and low complexity elements were less frequent. Best discrimination between both groups was achieved by total number of H3K9me3 reads (AUC 0.90) and H3K9me3 LINE elements L1 (AUC 0.93) und L2 (AUC 0.91). The present results confirm earlier findings of lower H3K9me3 levels in CRC and show LINE elements to be the most frequent and best discriminative markers on modified histones.