HPV infection results in changes in host gene methylation which, in turn, are thought to contribute to the neoplastic progression of HPV-associated cancers. The objective of this study was to identify joint and disease-specific genome-wide methylation changes in anal and cervical cancer as well as changes in high-grade pre-neoplastic lesions. Formalin-fixed paraffin-embedded (FFPE) anal tissues (n = 143; 99% HPV+) and fresh frozen cervical tissues (n = 28; 100% HPV+) underwent microdissection, DNA extraction, HPV genotyping, bisulfite modification, DNA restoration (FFPE) and analysis by the Illumina HumanMethylation450 Array. Differentially methylated regions (DMR; t test q<0.01, 3 consecutive significant CpG probes and mean Δβ methylation value>0.3) were compared between normal and cancer specimens in partial least squares (PLS) models and then used to classify anal or cervical intraepithelial neoplasia-3 (AIN3/CIN3). In AC, an 84-gene PLS signature (355 significant probes) differentiated normal anal mucosa (NM; n = 9) from AC (n = 121) while a 36-gene PLS signature (173 significant probes) differentiated normal cervical epithelium (n = 10) from CC (n = 9). The CC progression signature was validated using three independent publicly available datasets (n = 424 cases). The AC and CC progression PLS signatures were interchangeable in segregating normal, AIN3/CIN3 and AC and CC and were found to include 17 common overlapping hypermethylated genes. Moreover, these signatures segregated AIN3/CIN3 lesions similarly into cancer-like and normal-like categories. Distinct methylation changes occur across the genome during the progression of AC and CC with overall similar profiles and add to the evidence suggesting that HPV-driven oncogenesis may result in similar non-random methylomic events. Our findings may lead to identification of potential epigenetic drivers of HPV-associated cancers and also, of potential markers to identify higher risk pre-cancerous lesions.