Purpose: Information on cancer recurrence is rarely available outside clinical trials. Wide exclusion criteria used in clinical trials tend to limit the generalizability of findings to the entire population of people living beyond a cancer disease. Therefore, population-level evidence is needed. The aim of this study was to develop and validate a register-based algorithm to identify patients diagnosed with recurrence after curative treatment of malignant melanoma. Patients and Methods: Indicators of recurrence were diagnosis and procedure codes recorded in the Danish National Patient Register and pathology results recorded in the Danish National Pathology Register. Medical records on recurrence status and recurrence date in the Danish Melanoma Database served as the gold standard to assess the accuracy of the algorithm. Results: The study included 1747 patients diagnosed with malignant melanoma; 95 (5.4%) were diagnosed with recurrence of malignant melanoma according to the gold standard. The algorithm reached a sensitivity of 93.7% (95% confidence interval (CI) 86.8–97.6), a specificity of 99.2% (95% CI: 98.6–99.5), a positive predictive value of 86.4% (95% CI: 78.2–92.4), and negative predictive value of 99.6% (95% CI: 99.2–99.9). Lin’s concordance correlation coefficient was 0.992 (95% CI: 0.989–0.996) for the agreement between the recurrence dates generated by the algorithm and by the gold standard. Conclusion: The algorithm can be used to identify patients diagnosed with recurrence of malignant melanoma and to establish the timing of recurrence. This can generate population-level evidence on disease-free survival and diagnostic pathways for recurrence of malignant melanoma.