Proteases are important enzymes involved in biological and pathological systems. We developed a proteomics-based method to identify protease substrates and their cleavage- sites directly. The principle of identification relies on labeling the new N-terminus generated by proteolysis with an affinity tag, that serves to enrich cleavage-site peptides for analysis by liquid chromatography coupled tandem mass spectrometry (LC-MS/MS). Spectra collected are searched against a relevant proteome database to identify the protein identities as well as the location of the labeled peptides. Each peptide is annotated based on the location and sequence of the peptide within the full- length protein sequence. In this way we assessed the endogenous proteolytic activity in E. coli, S. cerevisiae, several mouse tissues, a human cell line, and human serum. A substantial proportion of the N-terminal peptides identified from all samples were full-length protein N- termini, as well as N-termini corresponding to co- translational proteolytic processing by well-characterized proteases. Yet, the majority of all N-termini corresponded to internal cleavage-sites, suggesting that proteolysis in vivo is much more prevalent than had previously been appreciated. A longstanding dogma in the protease field states that proteases only cleave substrates in regions lacking secondary structure. We reasoned that N- terminomics could challenge this dogma by identifying human caspase-3 and Staphylococcal glutamyl endopeptidase cleavage-sites from the structurally diverse and well- characterized folded protein library contained within E. coli lysate without bias in regard to the structures cleaved. Our analysis revealed that both proteases cleaved E. coli proteins in unstructured loops as well as \[alpha\]- helices, but almost never in \[Beta\]-strands. Many E. coli substrates of caspase-3 were recombinantly expressed and purified, and kinetically analyzed by in vitro assay, revealing that E. coli substrates were kinetically inferior to natural caspase-3 substrates. This kinetic deficiency was successfully overcome by engineering a poor E. coli substrate cleavage-site with the optimal amino acid sequence within an extended flexible loop. These results show that although helices can be cleaved by proteases, the natural substrates of caspase-3 have co- evolved with this protease resulting in efficient cleavage of near-optimal amino acid sequences positioned within flexible loop structures.