Inefficiency of gene delivery, together with inadequate bystander killing, represent two major hurdles in the development of a toxin-mediated gene therapy for human malignancy. The product of the Escherischia coli DeoD gene (purine nucleoside phosphorylase, PNP) differs from the mammalian enzyme in its substrate specificity and is capable of catalyzing the conversion of several non-toxic deoxyadenosine analogs to highly toxic adenine analogs. We have found that expression of E. coli PNP in <1% of a human colonic carcinoma cell line leads to the death of virtually all bystander cells after treatment with 6-methylpurine-2′-deoxyribonucleoside, a deoxyadenosine analog that is a substrate for E. coli PNP but not human PNP. Minimal toxicity was observed in non-transfected or E. coli LacZ transfected cells that were treated with this compound. These results establish a rational approach to achieve significant bystander killing, even after gene transfer to only a small fraction of tumor cells.