Effective proteome-wide strategies that distinguish the N-termini of proteins from the N-termini of their protease cleavage products would accelerate identification of the substrates of proteases with broad or unknown specificity. Our approach, named terminal amine isotopic labeling of substrates (TAILS), addresses this challenge by using dendritic polyglycerol aldehyde polymers that remove tryptic and C-terminal peptides. We analyze unbound naturally acetylated, cyclized or labeled N-termini from proteins and their protease cleavage products by tandem mass spectrometry, and use peptide isotope quantification to discriminate between the substrates of the protease of interest and the products of background proteolysis. We identify 731 acetylated and 132 cyclized N-termini, and 288 matrix metalloproteinase (MMP)-2 cleavage sites in mouse fibroblast secretomes. We further demonstrate the potential of our strategy to link proteases with defined biological pathways in complex samples by analyzing mouse inflammatory bronchoalveolar fluid and showing that expression of the poorly defined breast cancer protease MMP-11 in MCF-7 human breast cancer cells cleaves both endoplasmin and the immunomodulator and apoptosis inducer galectin-1.