In this study, proteogenomic analysis coupled with clinical histopathology revealed proteomic subtypes and identified candidate markers, which uncovered tumor biology related to patient survival. A total of 12,695 proteins and 45,356 phosphosites were quantified. This newly generated proteomic data was integrated with a previously published transcriptomic dataset from matched tumor specimens (Cirenajwis et al., 2015). Using consensus clustering, we could identify five melanoma subtypes, which were classified into extracellular, extracellular-immune, mitochondrial, mitochondrial-immune, and extracellular-mitochondrial categories according to/based on the annotations of their highly expressed proteins. The proteomic subtypes displayed differences in phenotype switching, immune surveillance, the levels of known melanoma markers, and were associated with survival. In addition, clinical parameters such as the expression of mutated BRAF V600E protein and the composition of the surrounding tumor microenvironment were found to be good independent indicators of prognosis. Lastly, validation of survival-related proteins in an independent cohort identified five candidate markers for predicting disease progression and patient survival (ADAM10, SCAI, CTNND1, CDK4, FGA). In conclusion, this study provides insights into the complex biology of melanoma while emphasizing/highlighting the importance of the tumor microenvironment. It also offers opportunities to find/indentify novel drug target candidates.