The purpose of this study was to assess the reproducibility and clinical impact of positron emission tomography (PET) with F-fluorodeoxyglucose (FDG) in patients with (suspected) recurrent melanoma. The clinical value of PET was prospectively measured in 58 consecutive patients referred for PET because of unresolved clinical questions after conventional work-up. Diagnostic understanding and therapy choice by referring physicians were evaluated before, directly after, and 6 months after PET. Observer agreement of PET readings was measured with respect to various parameters (interpretation, number and localization of lesions, ‘clinically decisive’ metastases), using intra-class correlation coefficients. FDG PET improved diagnostic understanding in 33 cases (57%). In six patients (10%), diagnostic understanding was solely based on PET information. According to the attending clinicians, PET contributed to a positive change of planned treatment in 23 patients (40%) and increased confidence in the chosen treatment in 23 (40%). Observer agreement of PET readings was very high (intra-class correlation coefficients were between 0.87 and 0.94). The diagnostic value related especially to the whole-body scan technique and the superior specificity, compared to conventional work-up. It is concluded that, in problematical cases with (suspected) recurrent melanoma, F-FDG PET had considerable impact on diagnostic understanding and management. Together with the excellent observer reliability, these results justify further studies to determine the optimal place of PET in routine diagnostic algorithms in recurrent melanoma.