Background: Patients with head and neck cancer (HNC) are vulnerable to fear of cancer recurrence (FCR) and psychiatric morbidity. We investigated the prevalence of high FCR and demographic, clinical, psychological, and psychiatric factors associated with high FCR prior to the start of the treatment. Methods: In a cross-sectional substudy of the large ongoing prospective NET-QUBIC study questionnaires and psychiatric interviews of 216 patients newly diagnosed with HNC were analyzed. Results: High FCR was observed in 52.8% of patients and among those 21.1% also had a lifetime history of selected anxiety or major depressive disorder. FCR was not related to any clinical characteristics; however, younger age, higher anxiety symptoms, introversion, greater needs for support regarding sexuality, and being an exsmoker were significantly associated with higher FCR. Conclusion: Factors associated with high FCR provide us with a better conceptual understanding of FCR in patients newly diagnosed with HNC.