Background: The role of S100B protein in detecting early melanoma relapses is controversial, since most metastasis occur within normal values of S100B. Objective: The aim of this study was to assess the performance of S100B in detecting early disease progression in high-risk melanoma patients. Methods: Retrospective cohort study including patients with an initial diagnosis of stage IIB, IIC and III melanoma between January 2003 and July 2013. All patients were followed up in accordance with an intensive protocol based on imaging studies and serum S100B levels every 3–6 months. We compared two methods to evaluate changes in S100B. The classic method referring to a single determination of S100B above the cut-off level at the time of metastasis, which was evaluated in all patients. And a new method based on monthly changes of S100, which was used in the setting of patients with S100B levels within the normal range. Results: Overall, 289 of patients were followed up for 44 months (IQR 17–73) and 45% developed metastases. During the study period, 129 patients relapsed of which 46 (35.7%) present elevated values of S100B at the time of relapse. The classic method had a sensitivity and specificity of S100B protein of 35.7% and 92.5%, respectively. Furthermore, for the patients that relapsed with normal values of S100B, the new method was applied and showed a sensitivity and specificity of 41.1% and 92.4%, respectively, allowing to detect additional relapses that were missing by the classic method. Conclusion: During follow-up of high-risk melanoma patients, rising serum S100B values within the normal range can be an important clue to disease progression.