(1) Background: The purpose of this retrospective study was to evaluate the recurrence and survival rates of metastatic melanoma of unknown primary origin (MUP), in order to further refine current recommendations for the surgical treatment; (2) Methods: Medical data of all MUP patients registered between 2000 and 2011, were analyzed. Seventy-eight patients were categorized in either lymph node (axilla, groin, head-and neck) or subcutaneous MUP. Axillary node MUPs were generally treated with dissections of levels I-III, inguinal node MUPs with combined superficial and deep groin dissections, and head-and-neck node MUPs with neck dissections to various extents, based on lymph drainage patterns. Subcutaneous lesions were excised with 1–2 cm margins. The primary outcome was treatment outcomes in terms of (loco)regional recurrence and survival rates; (3) Results: Lymph node MUP recurred regionally in 11% of patients, with an overall recurrence rate of 45%. In contrast, subcutaneous MUP recurred locally in 65% of patients with an overall recurrence rate of 78%. This latter group had a significantly shorter disease-free interval than patients with lymph node MUP (p = 0.000). In the entire study population, 5-year and 10-year overall survival rates were 56% and 47% respectively, with no differences observed between the various subgroups; (4) Conclusion: The relatively low regional recurrence rate after regional lymph node dissection (11%) supports its current status as standard surgical treatment for lymph node MUP. Subcutaneous MUP, on the contrary, appears to recur both locally (65%) and overall (78%) at a significantly higher rate, suggesting a different biological behavior. However, wide local excision remains the best available option for this specific group.