Although chemotherapy induces complete remission in the majority of acute myeloid leukemia (AML) patients, many face a relapse. This relapse is caused by survival of chemotherapy-resistant leukemia (stem) cells (measurable residual disease; MRD). Here, we demonstrate that the anthracycline doxorubicin epigenetically reprograms leukemia cells by inducing histone 3 lysine 27 (H3K27) and H3K4 tri-methylation. Within a doxorubicin-sensitive leukemia cell population, we identified a subpopulation of reversible anthracycline-tolerant cells (ATCs) with leukemic stem cell (LSC) features lacking doxorubicin-induced H3K27me3 or H3K4me3 upregulation. These ATCs have a distinct transcriptional landscape than the leukemia bulk and could be eradicated by KDM6 inhibition. In primary AML, reprogramming the transcriptional state by targeting KDM6 reduced MRD load and survival of LSCs residing within MRD, and enhanced chemotherapy response . Our results reveal plasticity of anthracycline resistance in AML cells and highlight the potential of transcriptional reprogramming by epigenetic-based therapeutics to target chemotherapy-resistant AML cells.