Herein we report the first proof for the application of type II 2′-deoxyribosyltransferase from Lactobacillus delbrueckii (LdNDT) in suicide gene therapy for cancer treatment. To this end, we first confirm the hydrolytic ability of LdNDT over the nucleoside-based prodrugs 2′-deoxy-5-fluorouridine (dFUrd), 2′-deoxy-2-fluoroadenosine (dFAdo), and 2′-deoxy-6-methylpurine riboside (d6MetPRib). Such activity was significantly increased (up to 30-fold) in the presence of an acceptor nucleobase. To shed light on the strong nucleobase dependence for enzymatic activity, different molecular dynamics simulations were carried out. Finally, as a proof of concept, we tested the LdNDT/dFAdo system in human cervical cancer (HeLa) cells. Interestingly, LdNDT/dFAdo showed a pronounced reduction in cellular viability with inhibitory concentrations in the low micromolar range. These results open up future opportunities for the clinical implementation of nucleoside 2′-deoxyribosyltransferases (NDTs) in cancer treatment.