The objective of this population-based study was to assess metastatic pathways and outcomes vs. selected clinical and histopathologic features of the primary tumor in patients with recurrent cutaneous malignant melanoma. At a median follow-up time of 11 years, 569/2493 patients with recurrence were identified. We demonstrated a 5-year survival rate of 82% and 30% among those with a primary local or regional recurrence, respectively. Patients with primary distant skin, distant lymph node, or pulmonary metastases had a significantly better survival compared with those with CNS, bone, visceral, liver, or multiple sites of first distant metastases. The metastatic pathways were similar with regard to histogenetic type, primary tumor thickness, Clark's level of invasion, and primary tumor ulceration. Different histogenetic types, as assessed by light microscopy, imply different risks of recurrence. However, once the recurrence is manifest, the metastatic pathways are uniform, as well as prognosis, and survival.