Cutaneous melanoma is the most dangerous skin cancer because of its ability to metastasize. Several clinical factors (number of invaded lymph nodes and/or presence of distant metastases) and histopathology (depth of tumor and presence of ulceration) are available to the clinician for determining prognosis and suggesting appropriate therapeutic management. However, these factors are often insufficient, especially in early forms of melanoma. Much research has focused on the identification of effective prognostic markers in serum. The only serum marker, which has been incorporated into the current AJCC classification for clinical use is lactate dehydrogenase dosage, a historical marker, restricted to the prognosis of metastatic disease. The recent development of technologies for proteome analysis offers new perspectives in this field. This review summarizes the specific considerations for each of the proteomic techniques used to date and presents the results of recent clinical investigations conducted to identify prognostic biomarkers in the serum of melanoma patients.