Histone H3 mono-ubiquitination, catalyzed by the RING E3 ubiquitin ligase UHRF1, is appreciated as a docking site for DNMT1 during DNA replication to facilitate DNA methylation maintenance. Its functions beyond this are unknown. Here, we identify simultaneous increases in UHRF1-dependent H3K18ub and SUV39H1/2-dependent H3K9me3 as prominent epigenetic alterations accompanying DNA hypomethylation induced by DNMT1 inhibition. Integrative epigenomics analyses reveal that transient accumulation of hemi-methylated DNA, resulting from incomplete DNA methylation maintenance, stimulates UHRF1-dependent H3K18ub at CpG islands that nucleates new domains of H3K9me3 and impedes PRC2 activity in these genomic regions. Notably, H3K18ub enhances the methyltransferase activity of SUV39H1/2, leading to increased H3K9me3 at these CpG island promoters. Blocking H3K18ub-dependent SUV39H1/2 activity enhances the efficacy of DNMT1 inhibitors. Collectively, these findings reveal a novel histone ubiquitination-methylation crosstalk mechanism that reinforces heterochromatin states in the absence of DNA methylation and proposes new strategies for improving cancer epigenetic therapy.