The purpose of this study was to examine whether staging with 18F-FDG PET/CT better predicts survival in patients with recurrent head and neck squamous cell carcinoma (HNSCC) than chest x-ray (CXR) plus head and neck MRI or chest CT (CCT) plus head and neck MRI. Methods: This was a prospective cohort study based on paired data. Consecutive patients with histologically verified HNSCC recurrence were enrolled from September 2013 to March 2016. All patients underwent CXR/MRI, CCT/MRI, and PET/CT on the same day and before biopsy. All imaging studies underwent masked interpretation by separate teams of experienced nuclear physicians or radiologists. Recurrent carcinomas were categorized as localized (equivalent to primary stages I–II), locally advanced (equivalent to primary stages III–IVB), or metastatic (equivalent to primary stage IVC). Discriminative abilities for each imaging strategy with respect to cancer-specific and stage-based survival were compared using Kaplan–Meier analysis, Cox proportional-hazards regression with the Harrell concordance index (C-index), and net reclassification improvement. Results: In total, 110 patients (90 men and 20 women; median age, 66 y; range, 40–87 y) were included. PET/CT significantly changed the assigned tumor stage when compared with imaging strategies based on CXR/MRI or CCT/MRI (P, 0.001 for both). Kaplan–Meier analysis of PET/CT-based staging showed progressively worsened prognosis with localized, locally advanced, or metastatic disease (log-rank test, P, 0.001), whereas CXR/MRI and CCT/MRI were unable to distinguish between these groups in terms of survival (log-rank test, P 5 0.18 and P 5 0.58, respectively). Overall discriminative ability in predicting cancer-specific mortality was significantly greater for PET/CT (C-index, 0.72) than for CXR/MRI (C-index, 0.55) (P 5 0.001) and CCT/MRI (C-index, 0.55)(P, 0.001). The addition of PET/CT to either CXR/MRI or CCT/MRI was associated with a significantly positive net reclassification improvement (P, 0.001 for both). Conclusion: Contrary to standard imaging strategies, PET/CT-based staging in recurrent HNSCC was able to significantly discriminate among the survival courses of patients with local, locally advanced, or metastatic disease and predict their respective survival probability.