The clinical stage anti-cancer agent PR-104 has potential utility as a cytotoxic prodrug for exogenous bacterial nitroreductases expressed from replicating vector platforms. However substrate selectivity is compromised due to metabolism by the human one- and two-electron oxidoreductases cytochrome P450 oxidoreductase (POR) and aldo-keto reductase 1C3 (AKR1C3). Using rational drug design we developed a novel mono-nitro analog of PR-104A that is essentially free of this off-target activity in vitro and in vivo. Unlike PR-104A, there was no biologically relevant cytotoxicity in cells engineered to express AKR1C3 or POR, under aerobic or anoxic conditions, respectively. We screened this inert prodrug analog, SN34507, against a type I bacterial nitroreductase library and identified E. coli NfsA as an efficient bioactivator using a DNA damage response assay and recombinant enzyme kinetics. Expression of E. coli NfsA in human colorectal cancer cells led to selective cytotoxicity to SN34507 that was associated with cell cycle arrest and generated a robust ‘bystander effect’ at tissue-like cell densities when only 3% of cells were NfsA positive. Anti-tumor activity of SN35539, the phosphate pre-prodrug of SN34507, was established in ‘mixed’ tumors harboring a minority of NfsA-positive cells and demonstrated marked tumor control following heterogeneous suicide gene expression. These experiments demonstrate that off-target metabolism of PR-104 can be avoided and identify the suicide gene/prodrug partnership of E. coli NfsA/SN35539 as a promising combination for development in armed vectors.