Despite recent developments in managing metastatic melanomas, patients' overall survival remains low. Therefore, the current study aims to understand better the proteome-wide changes associated with melanoma metastasis that will assist with identifying targeted therapies. The latest development in mass spectrometry-based proteomics, together with extensive bioinformatics analysis, was used to investigate the molecular changes in 60 formalin-fixed and paraffin-embedded samples of primary and lymph nodes (LN) and distant organ metastatic melanomas. A total of 4631 proteins were identified, of which 72 and 453 were significantly changed between the LN and distant organ metastatic melanomas compared to the primary lesions (adj. p-value <0.05). An increase in proteins such as SLC9A3R1, CD20 and GRB2 and a decrease in CST6, SERPINB5 and ARG1 were associated with regional LN metastasis. By contrast, increased metastatic activities in distant organ metastatic melanomas were related to higher levels of CEACAM1, MC1R, AKT1 and MMP3-9 and decreased levels of CDKN2A, SDC1 and SDC4 proteins. Furthermore, machine learning analysis classified the lesions with up to 92% accuracy based on their metastatic status. The findings from this study provide up to date proteome-level information about the progression of melanomas to regional LN and distant organs, leading to the identification of protein signatures with potential for clinical translation.