The aim of our study was to compare the overall and site-based accuracy and impact on patient management of positron emission tomography/computed tomography (PET/CT) and whole-body (wb) magnetic resonance imaging (MRI) in staging of advanced melanoma. In a prospective blinded study, 64 patients with American Joint Committee on Cancer (AJCC) stage III/IV melanoma underwent 18F-fluorodeoxyglucose PET/CT and wbMRI. In total 420 lesions were evaluated. The overall accuracy of PET/CT was 86.7% compared to 78.8% for wbMRI (P = 0.0007). PET/CT was significantly more accurate in N-staging and detecting of skin and subcutaneous metastases, whereas wbMRI was more sensitive in detecting liver, bone and brain metastases. WbMRI was less sensitive but more specific than PET/CT in classifying pulmonary lesions. In 41 patients (64%) whole-body imaging caused changes of treatment. Whole-body staging of patients with advanced melanoma is most accurate by combining wbPET/CT and organ-specific wbMRI including a brain, liver and bone marrow protocol.