In this case report, two patients with metastases from melanoma after a disease-free period of 34 years are presented. In 1983, both patients were treated for melanoma on the lower extremity with wide local excision. In 2017, they experienced unnecessary waiting time and examinations before being diagnosed. A follow-up time of many years for all melanoma patients may not be feasible, however, both patients and physicians must be aware of the potential for late metastases. In the case of new tumours of unknown origin we suggest a diagnostic approach: once melanoma, always melanoma, until the opposite has been proven.