Currently clinical outcome in melanoma is not predictable by known serum biomarkers. The only reliable tool for the diagnosis of this tumor is the histopathological assay after surgical removing. We used a proteomic approach in order to identify novel non-invasive serum biomarkers of melanoma. Serum proteomic maps showed different patterns in relation to the presence and progression of the tumor in five regions of the map. Differently expressed spots were identified by MALDI-TOF mass spectrometry. Significant increases of expression were found for transthyretin (TTR) and angiotensinogen (AGT) while vitamin D binding protein (DBP) expression was decreased in presence of melanoma. Interestingly, protein expression came back to control values in stages I and II of the disease after 1 month since surgical removal of suspected melanoma. We related the decrease of DBP spot to the impaired immune response of cancer patients. In fact cancer cells release the alpha-N-acetylgalactosaminidase that can deglycosylate DBP thus interfering with the immune cascade response in which DBP is involved, leading to immunosuppression in melanoma patients. Specific enzymatic activity of serum alpha-N-acetylgalactosaminidase was significantly increased in stage III melanoma patients, but not in early stages. This enzymatic assay may provide a non-invasive way of evaluation of melanoma severity.