The discovery of novel protein biomarkers in melanoma is crucial. Our introduction of formalin-fixed paraffin-embedded (FFPE) tumor protocol provides new opportunities to understand the progression of melanoma and open the possibility to screen thousands of FFPE samples deposited in tumor biobanks and available at hospital pathology departments. In our retrospective biobank pilot study, 90 FFPE samples from 77 patients were processed. Protein quantitation was performed by high-resolution mass spectrometry and validated by histopathologic analysis. The global protein expression formed six sample clusters. Proteins such as TRAF6 and ARMC10 were upregulated in clusters with enrichment for shorter survival, and proteins such as AIFI1 were upregulated in clusters with enrichment for longer survival. The cohort’s heterogeneity was addressed by comparing primary and metastasis samples, as well comparing clinical stages. Within immunotherapy and targeted therapy subgroups, the upregulation of the VEGFA-VEGFR2 pathway, RNA splicing, increased activity of immune cells, extracellular matrix, and metabolic pathways were positively associated with patient outcome. To summarize, we were able to (i) link global protein expression profiles to survival, and they proved to be an independent prognostic indicator, as well as (ii) identify proteins that are potential predictors of a patient’s response to immunotherapy and targeted therapy, suggesting new opportunities for precision medicine developments.