(1) Background: Prostate cancer (PCa) is characterized by high heterogeneity. The aim of this study was to investigate molecular alterations underlying PCa development based on proteomics data. (2) Methods: Liquid chromatography coupled to tandem mass spectrometry was conducted for 22 fresh-frozen tissue specimens from patients with benign prostatic hyperplasia (BPH, n = 5) and PCa (n = 17). Mann Whitney test was used to define significant differences between the two groups. Association of protein abundance with PCa progression was evaluated using Spearman correlation, followed by verification through investigating the Prostate Cancer Transcriptome Atlas. Functional enrichment and interactome analysis were carried out using Metascape and String. (3) Results: Proteomics analysis identified 1433 proteins, including 145 proteins as differentially abundant between patients with PCa and BPH. In silico analysis revealed alterations in several pathways and hallmarks implicated in metabolism and signalling, represented by 67 proteins. Among the latter, 21 proteins were correlated with PCa progression at both the protein and mRNA levels. Interactome analysis of these 21 proteins predicted interactions between Myc proto-oncogene (MYC) targets, protein processing in the endoplasmic reticulum, and oxidative phosphorylation, with MYC targets having a central role. (4) Conclusions: Tissue proteomics allowed for characterization of proteins and pathways consistently affected during PCa development. Further validation of these findings is required.