Most next generation sequencing experiments generate more data than is required for the experimental set up. For example, methyl-CpG binding domain (MBD) affinity purification based sequencing is often used for DNA-methylation profiling, but up to 30% of the sequenced fragments cannot be mapped uniquely to the reference genome. Here we present and evaluate a methodology for the identification of viruses in these otherwise unused paired-end MBD-seq data. Viral detection is accomplished by mapping non-reference alignable reads to a comprehensive set of viral genomes. As viruses play an important role in epigenetics and cancer development, 92 (pre)malignant and benign samples, originating from two different collections of cervical samples and related cell lines, were used in this study. These samples include primary carcinomas (n=22), low- \& high-grade cervical intrapeithelial neoplasia (CIN1 & CIN2/3 - n=2/n=30) and normal tissue (n=20), as well as control samples (n=17). Viruses that were detected include phages, adenoviruses, herpesviridae and HPV. HPV, which causes virtually all cervical cancers, was identified in 95% of the carcinomas, 100% of the CIN2/3 samples, both CIN1 samples and in 55% of the normal samples. Comparing the amount of mapped fragments on HPV for each HPV-infected sample yielded a significant difference between normal samples and carcinomas or CIN2/3 samples (adjusted p-values resp. < 10^-5, < 10^-5), reflecting different viral loads and/or methylation degrees in non-normal samples. Fragments originating from different HPV types could be distinguished and were independently validated by PCR-based assays with a specificity of 98% and a sensitivitity of 66%. In conclusion, although limited by the a priori knowledge of viral reference genome sequences, the proposed methodology can provide a first but substantial insight into the presence, concentration and types of methylated viral sequences in MBD-seq data without additional costs.