Introduction: No standard protocol for surveillance for melanoma patients is established. Whole-body magnetic resonance imaging (whole-body MRI) is a safe and sensitive technique that avoids exposure to X-rays and contrast agents. This prospective study explores the use of whole-body MRI for the early detection of recurrences. Material and Methods: Patients with American Joint Committee on Cancer Staging Manual (seventh edition; AJCC-7) stages IIIb/c or -IV melanoma who were disease-free following resection of macrometastases (cohort A), or obtained a durable complete response (CR) or partial response (PR) following systemic therapy (cohort B), were included. All patients underwent whole-body MRI, including T1, Short Tau Inversion Recovery, and diffusion-weighted imaging, every 4 months the first 3 years of follow-up and every 6 months in the following 2 years. A total body skin examination was performed every 6 months. Results: From November 2014 to November 2019, 111 patients were included (four screen failures, cohort A: 68 patients; cohort B: 39 patients). The median follow-up was 32 months. Twenty-six patients were diagnosed with suspected lesions. Of these, 15 patients were diagnosed with a recurrence on MRI. Eleven suspected lesions were considered to be of non-neoplastic origin. In addition, nine patients detected a solitary subcutaneous metastasis during self-examination, and two patients presented in between MRIs with recurrences. The overall sensitivity, specificity, positive predictive value, negative predictive value, and accuracy were, respectively, 58%, 98%, 58%, 98%, and 98%. Sensitivity and specificity for the detection of distant metastases was respectively 88% and 98%. No patient experienced a clinically meaningful (>grade 1) adverse event. Conclusions: Whole-body MRI for the surveillance of melanoma patients is a safe and sensitive technique sparing patients' cumulative exposure to X-rays and contrast media.