Proteomics screening methods for the identification of diagnostic and prognostic biomarkers in cancer are still lagging behind DNA- or RNA-based analysis. We used two-dimensional differential gel electrophoresis (2D-DIGE) in combination with laser capture microdissection (LCM) and MALDI-TOF/TOF mass spectrometry to determine differentially abundant proteins and candidate biomarkers in prostate cancer. Paired (benign and tumor) samples were isolated from 23 Gleason Score 6 (GS 6) and 23 Gleason Score 8 and higher (GS 8+) radical prostatectomy specimens and subjected to 2D-DIGE analysis. Minimal fluorescent dye labeling was applied and electrophoresis performed with triple samples (paired benign and tumor; internal control) for each case of tumor. Nineteen differently abundant proteins were identified by mass spectrometry and further validated. One half of them were associated with glycolysis and the Warburg effect; these were upregulated in tumors. The upregulation correlated with tumor dedifferentiation and might be relevant for selection of therapeutic strategies. Among the other proteins, heat shock protein 60 (HSP60) was significantly upregulated in tumor tissue compared to its benign counterpart. Furthermore, lamin A was statistically highly discriminatory between low and high Gleason score tumors and might serve as a new biomarker of tumor differentiation and prognosis.