Metastatic melanoma, the primary cause of skin cancer-related death, warrants new diagnostic and therapeutic approaches that target the regulatory machinery at molecular level. The heterogeneity and complexity of melanoma result in the difficulty to find biomarkers and targets for early detection and treatment. Here, we investigated metastasis-associated proteins by comparing the proteomic profiles of primary cutaneous melanomas to their matched lymph node metastases, which minimizes heterogeneity among samples from different patients. Results of two-dimensional gel electrophoresis (2-DE) followed by proteomic analysis revealed eight differentially expressed proteins. Among them, seven proteins (α-enolase, cofilin-1, LDH, m-β-actin, Nm23, GRP78, and MDA-9) showed increased and one (annexin A2) showed decreased expression in metastatic lymph node tissues than in primary melanomas. MDA-9 and GRP78 were the most highly expressed proteins in lymph node metastases, which was validated by immunohistochemical staining. Moreover, exosomes from serum samples of metastatic melanoma patients contained higher levels of MDA-9 and GRP78 than those of patients without metastases, indicating the potential of MDA-9 and GRP78 to be biomarkers for early detection of metastasis. Further, small interfering RNA (siRNA)-mediated knockdown confirmed a functional role for MDA-9 and GRP78 to promote cell invasion in the A375 cells. Finally, we showed that GRP78 co-localized with MDA-9 in 293T cells. Taken together, our findings support MDA-9, co-expressed with GRP78, as a melanoma protein associated with lymph node metastasis. Investigating how MDA-9 and GRP78 interact to contribute to melanoma metastasis and disease progression could reveal new potential avenues of targeted therapy and/or useful biomarkers for diagnosis and prognosis.