Matrix metalloproteinase-9 (MMP-9) is implicated in tumor metastasis as well as a variety of inflammatory and pathological processes. Although many substrates for MMP-9, including components of the extracellular matrix, soluble mediators such as chemokines, and cell surface molecules have been identified, we undertook a more comprehensive proteomics-based approach to identify new substrates to further understand how MMP-9 might contribute to tumor metastasis. Previous proteomics approaches to identify protease substrates have depended upon differential labeling of each sample. Instead we used a label-free quantitative proteomics approach based on ultraperformance LC-ESI-high/low collision energy MS. Conditioned medium from a human metastatic prostate cancer cell line, PC-3ML, in which MMP-9 had been down-regulated by RNA interference was compared with that from the parental cells. From more than 200 proteins identified, 69 showed significant alteration in levels after depletion of the protease (>+/-2-fold), suggesting that they might be candidate substrates. Levels of six of these (amyloid-beta precursor protein, collagen VI, leukemia inhibitory factor, neuropilin-1, prostate cancer cell-derived growth factor (PCDGF), and protease nexin-1 (PN-1)) were tested in the conditioned media by immunoblotting. There was a strong correlation between results by ultraperformance LC-ESI-high/low collision energy MS and by immunoblotting giving credence to the label-free approach. Further information about MMP-9 cleavage was obtained by comparison of the peptide coverage of collagen VI in the presence and absence of MMP-9 showing increased sensitivity of the C- and N-terminal globular regions over the helical regions. Susceptibility of PN-1 and leukemia inhibitory factor to MMP-9 degradation was confirmed by in vitro incubation of the recombinant proteins with recombinant MMP-9. The MMP-9 cleavage sites in PN-1 were sequenced. This study provides a new label-free method for degradomics cell-based screening leading to the identification of a series of proteins whose levels are affected by MMP-9, some of which are clearly direct substrates for MMP-9 and become candidates for involvement in metastasis.