The contribution of early virus induced epigenetic changes to human papillomavirus (HPV) associated carcinogenesis is poorly understood. Using genome-wide methylation array profiling and a cell-based model which supports replication of HPV episomes, we found that transfection of primary human foreskin keratinocytes with episomal forms of high-risk HPV types was followed by up-regulation of the DNA methyltransferases, DNMT1 and DNMT3B, and changes in the methylation status of cellular genes many of which are reported to be differentially methylated in cervical neoplasia. HPV16 and HPV18 associated changes were not randomly distributed across the genome but clustered at specific chromosomal locations which mapped on to known HPV integration sites and to chromosomal regions lost and gained in high-grade cervical neoplasia. Methylation changes were directed in part by the same cis-acting factors which appear to direct methylation changes in cancer, the presence of a bivalent chromatin mark in human embryonic stem cells and promoter CpG content; these associations explain much of the ontological profile of genes found to have increased methylation following HPV16 transfection. We were also able to show using sequential samples from a cohort of young women with incident HPV16 infections that the detection in cervical samples of methylated forms of the tumour suppressor gene, RARB, often parallels the natural history of cervical HPV infection. Our findings suggest that further investigation of the distribution and determinants of early virus induced epigenetic reprogramming, will provide important insights into the pathogenesis of virus associated malignancy.