Updated project metadata. Stable inheritance of DNA methylation is critical for maintaining the differentiated phenotypes in multicellular organisms. However, the molecular basis ensuring high fidelity of maintenance DNA methylation is largely unknown. Here, we demonstrate that two distinct modes of DNMT1 recruitment, one is DNA replication-coupled and the other is uncoupled mechanism, regulate the stable inheritance of DNA methylation. PCNA-associated factor 15 (PAF15) represents a primary target of UHRF1 and undergoes dual mono-ubiquitylation (PAF15Ub2) on chromatin. PAF15Ub2 specifically interacts with DNMT1 and controls the recruitment of DNMT1 in a DNA replication-coupled manner. Thus, loss of PAF15Ub2 results in impaired DNA methylation at sites replicating during early S phase. In contrast, outside of S phase or when PAF15 ubiquitylation is perturbed, UHRF1 ubiquitylates histone H3 to promote DNMT1 recruitment. Together, we identify replication-coupled and uncoupled mechanisms of maintenance DNA methylation, both of which collaboratively ensure the stable DNA methylation.