Proteases are a family of proteolytically active enzymes whose dysfunction is implicated in a wide variety of human diseases. Although an estimated 2% of the human genome encodes for proteases, only a small fraction of these enzymes have well-characterized functions. Identification of the specificity and natural substrates of proteases in complex biological samples is challenging, but proteomic screens for proteases are currently experiencing impressive progress. Such proteomic screens include peptide-based libraries, fluorescent 2D difference gel electrophoresis with mass spectrometry, differential isotope labeling in combination with mass spectrometry, quantitative degradomics analysis of proteolytically generated neo-N-termini, and activity-based protein profiling. In the present article, we summarize and discuss the current status of proteomic techniques to identify protease specificity, cleavage sites and natural substrates with a particular focus on the cytotoxic lymphocyte granule serine proteases granzymes.