Proteolysis is a major protein posttranslational modification that, by altering protein structure, affects protein function and, by truncating the protein sequence, alters peptide signatures of proteins analyzed by proteomics. To identify such modified and shortened protease-generated neo-N-termini on a proteome-wide basis, we developed a whole protein isobaric tag for relative and absolute quantitation (iTRAQ) labeling method that simultaneously labels and blocks all primary amines including protein N- termini and lysine side chains. Blocking lysines limits trypsin cleavage to arginine, which effectively elongates the proteolytically truncated peptides for improved MS/MS analysis and peptide identification. Incorporating iTRAQ whole protein labeling with terminal amine isotopic labeling of substrates (iTRAQ-TAILS) to enrich the N-terminome by negative selection of the blocked mature original N-termini and neo-N-termini has many advantages. It enables simultaneous characterization of the natural N-termini of proteins, their N-terminal modifications, and proteolysis product and cleavage site identification. Furthermore, iTRAQ-TAILS also enables multiplex N-terminomics analysis of up to eight samples and allows for quantification in MS2 mode, thus preventing an increase in spectral complexity and extending proteome coverage by signal amplification of low abundance proteins. We compared the substrate degradomes of two closely related matrix metalloproteinases, MMP-2 (gelatinase A) and MMP-9 (gelatinase B), in fibroblast secreted proteins. Among 3,152 unique N-terminal peptides identified corresponding to 1,054 proteins, we detected 201 cleavage products for MMP-2 and unexpectedly only 19 for the homologous MMP-9 under identical conditions. Novel substrates identified and biochemically validated include insulin-like growth factor binding protein-4, complement C1r component A, galectin-1, dickkopf-related protein-3, and thrombospondin-2. Hence, N-terminomics analyses using iTRAQ-TAILS links gelatinases with new mechanisms of action in angiogenesis and reveals unpredicted restrictions in substrate repertoires for these two very similar proteases.