High-risk human papillomavirus (hrHPV)-induced immortalization and malignant transformation are accompanied by DNA methylation of host genes. To determine when methylation is established during cell immortalization and whether it is hrHPV-type dependent, DNA methylation was studied in a large panel of HPVE6E7-immortalized keratinocyte cell lines. These cell lines displayed different growth behaviors, i.e., continuous growth versus crisis period prior to immortalization, reflecting differential immortalization capacities of the 7 HPV-types (16/18/31/33/45/66/70) studied. In this study, cells were monitored for hypermethylation of 14 host genes (APC, CADM1, CYGB, FAM19A4, hTERT, mir124–1, mir124–2, mir124–3, MAL, PHACTR3, PRDM14, RASSF1A, ROBO3, and SFRP2) at 4 different stages during immortalization. A significant increase in overall methylation levels was seen with progression through each stage of immortalization. At stage 1 (pre-immortalization), a significant increase in methylation of hTERT, mir124–2, and PRDM14 was already apparent, which continued over time. Methylation of ROBO3 was significantly increased at stage 2 (early immortal), followed by CYGB (stage 3) and FAM19A4, MAL, PHACTR3, and SFRP2 (stage 4). Methyation patterns were mostly growth behavior independent. Yet, hTERT methylation levels were significantly increased in cells that just escaped from crisis. Bisulfite sequencing of hTERT confirmed increased methylation in immortal cells compared to controls, with the transcription core and known repressor sites remaining largely unmethylated. In conclusion, HPV-induced immortalization is associated with a sequential and progressive increase in promoter methylation of a subset of genes, which is mostly independent of the viral immortalization capacity.