Acute myeloid leukemia (AML) patients display dismal prognosis due to high prevalence of refractory and relapsed disease resulting from chemoresistance. Treatment protocols, primarily based on the anchor drug Cytarabine, remained chiefly unchanged in the past 50 years with no standardized salvage regimens. Herein we aimed at exploring potential pre-clinical treatment strategies to surmount Cytarabine resistance in human AML cells. We established Cytarabine-resistant sublines derived from human leukemia K562 and Kasumi cells, and characterized the expression of Cytarabine-related genes using real-time PCR and Western blot analyses to uncover the mechanisms underlying their Cytarabine resistance. This was followed by growth inhibition assays and isobologram analyses testing the sublines' sensitivity to the clinically approved drugs hydroxyurea (HU) and azidothymidine (AZT), compared to their parental cells. All Cytarabine-resistant sublines lost deoxycytidine kinase (dCK) expression, rendering them refractory to Cytarabine. Loss of dCK function involved dCK gene deletions and/or a novel frameshift mutation leading to dCK transcript degradation via nonsense-mediated decay. Cytarabine-resistant sublines displayed hypersensitivity to HU and AZT compared to parental cells; HU and AZT combinations exhibited a marked synergistic growth inhibition effect on leukemic cells, which was intensified upon acquisition of Cytarabine-resistance. In contrast, HU and AZT combination showed an antagonistic effect in non-malignant cells. Finally, HU and AZT synergism was demonstrated on peripheral blood specimens from AML patients. These findings identify a promising HU and AZT combination for the possible future treatment of relapsed and refractory AML, while sparing normal tissues from untoward toxicity.