(1) Background: Patients with locally advanced head and neck squamous cell carcinoma (HNSCC) who are biologically at high risk for the development of loco-regional recurrences after postoperative radiotherapy (PORT) but at intermediate risk according to clinical risk factors may benefit from additional concurrent chemotherapy. In this matched-pair study, we aimed to identify a corresponding predictive gene signature. (2) Methods: Gene expression analysis was performed on a multicenter retrospective cohort of 221 patients that were treated with postoperative radiochemotherapy (PORT-C) and 283 patients who were treated with PORT alone. Propensity score analysis was used to identify matched patient pairs from both cohorts. From differential gene expression analysis and Cox regression, a predictive gene signature was identified. (3) Results: 108 matched patient pairs were selected. We identified a 2-metagene signature that stratified patients into risk groups in both cohorts. The comparison of the high-risk patients between the two types of treatment showed higher loco-regional control (LRC) after treatment with PORT-C ( p < 0.001), which was confirmed by a significant interaction term in Cox regression ( p = 0.027), i.e., the 2-metagene signature was indicative for the type of treatment. (4) Conclusion: We have identified a novel gene signature that may be helpful to identify patients with high-risk HNSCC amongst those at intermediate clinical risk treated with PORT, who may benefit from additional concurrent chemotherapy.