E6 from high-risk strains of HPV is well known to transform cells by deregulating p53. We reported that in HPV transformed cell-lines E6 from high-risk HPV can recruit the USP46 deubiquitinase to substrates such as Cdt2 and stabilize the latter, and that USP46 is important for growth of HPV induced tumors in xenografts. Here we show that in cervical cancer biopsies the stabilization of Cdt2 in the HPV-induced cancers leads to the decrease of a CRL4-Cdt2 substrate, the histone H4K20 mono-methyltransferase Set8, and decrease in H4K20me1 or H4K20me3 that can be detected by immunohistochemistry. In HPV-transformed cancer cell lines in vitro, knockdown of E6 decreases Cdt2 and increases Set8. Co-knockdown of Set8 shows that some of the gene expression changes produced by E6 knockdown is due to the increase of Set8. EGFR and EGFR regulated genes were identified in this set of genes. Turning to the mechanism by which E6 stabilizes Cdt2, we find that a purified E6:USP46 complex has significantly more de-ubiquitinase activity in vitro than USP46 alone, demonstrating that E6 can directly interact with USP46 in the absence of other proteins and that it can substitute for the known activators of USP46, UAF1 and WDR20. Deletion mapping of Cdt2 shows that there are three discrete, but redundant, parts of the substrate that are essential for stabilization by E6: USP46. The helix–loop–helix region or the WD40 repeat driven beta-propeller structure of Cdt2 are dispensable for the stabilization implying that interaction with DDB1 (and the rest of the CRL4 complex) or with the substrate of the CRL4-Cdt2 E3 ligase is not necessary for E6:USP46 to interact with and stabilize Cdt2. The identification of 50 amino acid stretches in the 731 amino acid Cdt2 protein as being important for the stabilization by E6 underlines the specificity of the process. In summary, E6 activates the deubiquitinase activity of USP46, stabilizes Cdt2 utilizing multiple sites on Cdt2, and leads to degradation of Set8 and changes in gene-expression in HPV-transformed cells.