Cervical cancer is a major health concern among women in Latin America due to its high incidence and mortality. Therefore, the discovery of molecular markers for cervical cancer screening and triage is imperative. The aim of this study was to use a genome wide DNA methylation approach to identify novel methylation biomarkers in cervical cancer. DNA from normal cervical mucosa and cervical cancer tissue samples from Chile was enriched with Methylated DNA Immunoprecipitation (MeDIP), hybridized to oligonucleotide methylation microarrays and analyzed with a stringent bioinformatics pipeline to identify differentially methylated regions (DMRs) as candidate biomarkers. Quantitative Methylation Specific PCR (qMSP) was used to study promoter methylation of candidate DMRs in clinical samples from two independent cohorts. HPV detection and genotyping were performed by Reverse Line Blot analysis. Bioinformatics analysis revealed GGTLA4, FKBP6, ZNF516, SAP130, and INTS1 to be differentially methylated in cancer and normal tissues in the Discovery cohort. In the Validation cohort FKBP6 promoter methylation had 73% sensitivity and 80% specificity (AUC = 0.80). ZNF516 promoter methylation was the best biomarker, with both sensitivity and specificity of 90% (AUC = 0.92), results subsequently corroborated in a Prevalence cohort. Together, ZNF516 and FKBP6 exhibited a sensitivity of 84% and specificity of 81%, when considering both cohorts. Our genome wide DNA methylation assessment approach (MeDIP-chip) successfully identified novel biomarkers that differentiate between cervical cancer and normal samples, after adjusting for age and HPV status. These biomarkers need to be further explored in case-control and prospective cohorts to validate them as cervical cancer biomarkers.