Background Prognostic factors in patients with localized primary cutaneous malignant melanoma (CMM) are well described. However, prognostic factors for recurrence are less documented. Objectives The aim of this study was to identify prognostic risk factors for first recurrence in patients with localized stages I-II CMM using population-based data. Methods This study included 1437 CMM patients registered in one region of Sweden during 1999-2012 follow-up through 31 December 2012. To identify first recurrence of CMM disease, data from a care data warehouse, the pathology and radiology department registries were used. Patients were also followed through a census register and the national Cause of Death Register. Results The 5- and 10-year recurrence-free survival (RFS) were 85.7% and 81.2%, respectively. The most common site of first recurrence was regional lymph node metastasis closely followed by distant metastasis. After adjusting for all prognostic factors, women had 50% lower risk of recurrence than men (HR = 0.5, 95% CI 0.4-0.7) and patients = 70 had higher risk compared to patients 55-69 years (HR = 1.7, 95% CI 1.2-2.5). Other significant prognostic factors for risk of recurrence were tumour thickness, presence of ulceration, Clarks level of invasion and histogenetic type. Conclusion Tumour thickness was found to be the predominant risk factor for recurrence. The prognostic factors for recurrence coincided with prognostic factors for CMM death. The most common site of first recurrence in stages I-II CMM is regional lymph node (42.8%) closely followed by distant metastases (37.6%), a fact which has to be taken into consideration when choosing follow-up strategies.