Multiple, complex molecular events characterize cancer development and progression. Deciphering the molecular networks that distinguish organ-confined disease from metastatic disease may lead to the identification of biomarkers of cancer invasion and disease aggressiveness. Although alterations in gene expression have been extensively quantified during neoplastic progression, complementary analyses of proteomic changes have been limited. Here we interrogate the proteomic alterations in a cohort of 15 prostate-derived tissues that included five each from adjacent benign prostate, clinically localized prostate cancer, and metastatic disease from distant sites. The experimental strategy couples isobaric tags for relative and absolute quantitation with multidimensional liquid phase peptide fractionation followed by tandem mass spectrometry. Over 1000 proteins were quantified across the specimens and delineated into clinically localized and metastatic prostate cancer-specific signatures. Included in these class-specific profiles were both proteins that were known to be dysregulated during prostate cancer progression and new ones defined by this study. Enrichment analysis of the prostate cancer-specific proteomic signature, to gain insight into the functional consequences of these alterations, revealed involvement of miR-128-a/b regulation during prostate cancer progression. This finding was validated using real time PCR analysis for microRNA transcript levels in an independent set of 15 clinical specimens. miR-128 levels were elevated in benign prostate epithelial cell lines compared with invasive prostate cancer cells. Knockdown of miR-128 induced invasion in benign prostate epithelial cells, whereas its overexpression attenuated invasion in prostate cancer cells. Taken together, our profiles of the proteomic alterations of prostate cancer progression revealed miR-128 as a potentially important negative regulator of prostate cancer cell invasion.