Decitabine (DAC), a well-recognized DNA hypomethylating agent, has been applied to treat acute myeloid leukemia. However, clinic investigations revealed that DNA methylation reduction does not correlate with a clinical response, and relapse is prevalent. To gain a better understanding of its anti-tumor mechanism, we perform a temporally resolved CRISPR-Cas9 screen to identify factors governing the DAC response. We show that DNA damage generated by DNMT-DNA adducts and 5-aza-dUTP misincorporation through the dCMP deaminase DCTD act as drivers of DAC-induced acute cytotoxicity. The DNA damage that arises during the next S phase is dependent on DNA replication, unveiling a trans-cell cycle effect of DAC on genome stability. By exploring candidates for synthetic lethality, we unexpectedly uncover that KDM1A promotes survival after DAC treatment through interactions with ZMYM3 and CoREST, independent of its demethylase activity or regulation of viral mimicry. These findings emphasize the importance of DNA repair pathways in DAC response and provide potential biomarkers.