Previously, we have shown that copy number gain of the chromosomal band 16q24.3 is associated with impaired clinical outcome of radiotherapy-treated head and neck squamous cell carcinoma (HNSCC) patients. We set out to identify a prognostic mRNA signature from genes located on 16q24.3 in radio(chemo)therapy-treated HNSCC patients of the TCGA (The Cancer Genome Atlas, n = 99) cohort. We applied stepwise forward selection using expression data of 41 16q24.3 genes. The resulting optimal Cox-proportional hazards regression model included the genes APRT, CENPBD1, CHMP1A, and GALNS. Afterward, the prognostic value of the classifier was confirmed in an independent cohort of HNSCC patients treated by adjuvant radio(chemo)therapy (LMU-KKG cohort). The signature significantly differentiated high- and low-risk patients with regard to overall survival (HR = 2.01, 95% CI 1.10–3.70; P = 0.02125), recurrence-free survival (HR = 1.84, 95% CI 1.01–3.34; P = 0.04206), and locoregional recurrence-free survival (HR = 1.87, 95% CI 1.03–3.40; P = 0.03641). The functional impact of the four signature genes was investigated after reconstruction of a gene association network from transcriptome data of the TCGA HNSCC cohort using a partial correlation approach. Subsequent pathway enrichment analysis of the network neighborhood (first and second) of the signature genes suggests involvement of HNSCC-associated signaling pathways such as apoptosis, cell cycle, cell adhesion, EGFR, JAK-STAT, and mTOR. Furthermore, a detailed analysis of the first neighborhood revealed a cluster of co-expressed genes located on chromosome 16q, substantiating the impact of 16q24.3 alterations in poor clinical outcome of HNSCC. The reported gene expression signature represents a prognostic marker in HNSCC patients following postoperative radio(chemo)therapy.