Objective: To investigate stage-specific survival from diagnosis, stage-specific disease recurrence, and post-recurrence survival in patients diagnosed with localized and regionally advanced cutaneous melanoma. Methods: A retrospective, observational cohort study was conducted in six Dutch hospitals. We included patients with a first diagnosis of stage I, II, or III melanoma between January 2003 and December 2011. Descriptive statistics were used to summarize time to first recurrence and type of first recurrence. Overall survival (OS) from diagnosis and post-recurrence OS were assessed using the Kaplan-Meier method. Results: A total of 3,093 patients had a first diagnosis of stage I (n = 2,299), II (n = 565), or III (n = 229) melanoma. Median OS was not yet reached for patients with stage I, 9.5 years for patients with stage II, and 6.8 years for patients with stage III. Fifty-seven patients (8%) with stage IB, 137 patients (29%) with stage II, and 81 patients (47%) with stage III developed disease recurrence. Median time to first recurrence was 2.8, 1.5, and 1.0 years for patients with stage IB, II, and III, respectively. Most patients (79%) developed regional lymph node or distant metastases as first recurrence. Median post-recurrence OS was 2.8, 3.9, and 0.5 years for patients with intralymphatic, regional lymph node, and distant metastases, respectively. Conclusion: A substantial number of patients developed disease recurrence. Of these patients, a considerably high proportion developed distant metastases which had a great impact on survival. Identifying disease recurrence at its earliest stage is crucial because metastatic melanoma remains incurable for most patients.