Two fundamental questions with regard to proteolytic networks and pathways concern the structural repertoire and kinetic threshold that distinguish legitimate signaling substrates. We used N-terminal proteomics to address these issues by identifying cleavage sites within the Escherichia coli proteome that are driven by the apoptotic signaling protease caspase-3 and the bacterial protease glutamyl endopeptidase (GluC). Defying the dogma that proteases cleave primarily in natively unstructured loops, we found that both caspase-3 and GluC cleave in alpha-helices nearly as frequently as in extended loops. Notably, biochemical and kinetic characterization revealed that E. coli caspase-3 substrates are greatly inferior to natural substrates, suggesting protease and substrate coevolution. Engineering an E. coli substrate to match natural catalytic rates defined a kinetic threshold that depicts a signaling event. This unique combination of proteomics, biochemistry, kinetics and substrate engineering reveals new insights into the structure-function relationship of protease targets and their validation from large-scale approaches.