Head and neck squamous cell carcinoma (HNSC) is one of most common types of cancer worldwide, and mRNAs and long non-coding RNAs (lncRNAs) have been identified as prognostic biomarkers in HNSC. In the present study, using gene expression datasets from multiple platforms, survival-associated genes in HNSC were identified. Subsequently, a combination of 17 genes (14 mRNAs and 3 lncRNA) was optimized using random forest variable hunting and a risk score model for HNSC prognosis was developed using a cohort from The Cancer Genome Atlas. Patients with high-risk scores tend to have earlier disease recurrence and lower survival rates, compared with those with low-risk scores. This observation was further validated in three independent datasets (GSE41613, GSE10300 and E-MTAB-302). Association analysis revealed that the risk score is independent of other clinicopathological observations. On the basis of the results depicted in the nomogram, the risk score performs better in 3-year survival rate prediction than other clinical observations. In summary, the lncRNA-mRNA signature-based risk score successfully predicts the survival of HNSC and serves as an indicator of prognosis.