Objective The benefit of FDG-PET/CT in follow-up of patients treated with adjuvant immunotherapy after resection of high-risk malignant melanoma (MM) is debated. This study evaluated the diagnostic accuracy and clinical impact of FDG-PET/CT for diagnosing MM recurrence during the first year after surgery. Methods We retrospectively included 124 patients with resected high-risk MM, who received adjuvant immunotherapy and follow-up FDG-PET/CT. Clinical information and AJCC-8 stage was obtained from patients’ medical records. Recurrence was verified by biopsy/progression on a subsequent scan leading to change of treatment. Non-recurrence was assumed when no metastases were observed until the subsequent follow-up scan. Incidence of recurrence, sensitivity, specificity, positive and negative predictive values (PPV and NPV) were outcome measures. Results Incidence rate of MM recurrence was 0.27 95% CI 0.17–0.37 per person-year during the first-year. Recurrence was detected in 13 patients (10%) at 3-month FDG-PET/CT, in 10 patients (8.1%) at 6 months, 1 patient (0.8%) at 9 months, 3 patients (2.4%) at 12 months. The overall sensitivity, specificity, PPV, and NPV were 97% 86–99, 82% 78–86, 39% 29–50, and 99% 98–99, respectively. The PPV trended towards higher values as disease stage increased. At the 3-month scan, the majority of actions derived from positive findings were surgery or earlier expedition of the subsequent follow-up scan. Conclusion The high rate of recurrence in patients with high-risk MM treated with adjuvant immunotherapy emphasizes the need for follow-up. The potential harm by a moderately low specificity reflecting a high number of false-positive results must be weighed against the benefit of early detection of recurrence.