Background: The incidence of malignant melanoma (MM) is steadily rising, with only a minor increase in mortality. At present, there is no consensus regarding recommendations for follow-up programmes for MM, and health care programmes currently involve different schedules. With increasing opportunities to administer successful treatment for early disseminated disease, it may be of interest to engage MM patients and/or relatives in self-control. Objectives: The aim of the present study was to analyse both the time to, and the location of, the first metastatic lesion in order to provide help for the patient, relatives, and health professionals, and ensure better follow-up. Materials and methods: Data from the Swedish Melanoma Register, pathology registers, and the Cause of Death Register were used. Patients from the south-east region diagnosed with primary cutaneous MM between 1993 and 2007 were selected and data were correlated to characteristics of the primary tumour. Results: Metastases developed in 421 of the 2,910 patients with primary cutaneous MM in Stage I and II of the disease. Thirty-five percent of all recurrences were detected during the first year. Time to first metastasis to the skin and lymph nodes was almost identical. Conclusion: The vast majority of the recurrences were diagnosed at sites that were easily recognised by the patient and relatives; self-examination may therefore be a worthwhile approach. Our findings further indicate that the follow-up programme should focus on the first three years after diagnosis.