Two potentially complementary approaches to improve the anti-cancer strategy gene-directed enzyme prodrug therapy (GDEPT) are discovery of more efficient prodrug-activating enzymes, and development of more effective prodrugs. Here we demonstrate the utility of a flexible screening system based on the Escherichia coli SOS response to evaluate novel nitroreductase enzymes and prodrugs in concert. To achieve this, a library of 47 candidate genes representing 11 different oxidoreductase families was created and screened to identify the most efficient activators of two different nitroaromatic prodrugs, CB1954 and PR-104A. The most catalytically efficient nitroreductases were found in the NfsA and NfsB enzyme families, with NfsA homologues generally more active than NfsB. Some members of the AzoR, NemA and MdaB families also exhibited low-level activity with one or both prodrugs. The results of SOS screening in our optimised E. coli reporter strain SOS-R2 were generally predictive of the ability of nitroreductase candidates to sensitise E. coli to CB1954, and of the kcat/Km for each prodrug substrate at a purified protein level. However, we also found that not all nitroreductases express stably in human (HCT-116 colon carcinoma) cells, and that activity at a purified protein level did not necessarily predict activity in stably transfected HCT-116. These results highlight a need for all enzyme-prodrug partners for GDEPT to be assessed in the specific context of the vector and cell line that they are intended to target. Nonetheless, our oxidoreductase library and optimised screens provide valuable tools to identify preferred nitroreductase-prodrug combinations to advance to preclinical evaluation.