Molecular profiling of cancer at the transcript level has become routine. Large-scale analysis of proteomic alterations during cancer progression has been a more daunting task. Here, we employed high-throughput immunoblotting in order to interrogate tissue extracts derived from prostate cancer. We identified 64 proteins that were altered in prostate cancer relative to benign prostate and 156 additional proteins that were altered in metastatic disease. An integrative analysis of this compendium of proteomic alterations and transcriptomic data was performed, revealing only 48%-64% concordance between protein and transcript levels. Importantly, differential proteomic alterations between metastatic and clinically localized prostate cancer that mapped concordantly to gene transcripts served as predictors of clinical outcome in prostate cancer as well as other solid tumors.