The number of known proteases is increasing at a tremendous rate as a consequence of genome sequencing projects. Although one can guess at the functions of these novel enzymes by considering sequence homology to known proteases, there is a need for new tools to rapidly provide functional information on large numbers of proteins. We describe a method for determining the cleavage site specificity of proteolytic enzymes that involves pooled sequencing of peptide library mixtures. The method was used to determine cleavage site motifs for six enzymes in the matrix metalloprotease (MMP) family. The results were validated by comparison with previous literature and by analyzing the cleavage of individually synthesized peptide substrates. The library data led us to identify the proteoglycan neurocan as a novel MMP-2 substrate. Our results indicate that a small set of libraries can be used to quickly profile an expanding protease family, providing information applicable to the design of inhibitors and to the identification of protein substrates.