Spores of some species of the strictly anaerobic bacteria Clostridium naturally target and partially lyse the hypoxic cores of tumors, which tend to be refractory to conventional therapies. The anti-tumor effect can be augmented by engineering strains to convert a non-toxic prodrug into a cytotoxic drug specifically at the tumor site by expressing a prodrug-converting enzyme (PCE). Safe doses of the favored prodrug CB1954 lead to peak concentrations of 6.3 µM in patient sera, but at these concentration(s) known nitroreductase (NTR) PCEs for this prodrug show low activity. Furthermore, efficacious and safe Clostridium strains that stably express a PCE have not been reported. Here we identify a novel nitroreductase from Neisseria meningitidis, NmeNTR, which is able to activate CB1954 at clinically-achievable serum concentrations. An NmeNTR expression cassette, which does not contain an antibiotic resistance marker, was stably localized to the chromosome of Clostridium sporogenes using a new integration method, and the strain was disabled for safety and containment by making it a uracil auxotroph. The efficacy of Clostridium-Directed Enzyme Prodrug Therapy (CDEPT) using this system was demonstrated in a mouse xenograft model of human colon carcinoma. Substantial tumor suppression was achieved, and several animals were cured. These encouraging data suggest that the novel enzyme and strain engineering approach represent a promising platform for the clinical development of CDEPT.