Head and neck squamous cell carcinoma (HNSCC) is a malignant tumor with a strong tendency for metastasis and recurrence. Finding effective biomarkers for the early diagnosis of HNSCC is critical for the early treatment and prognosis of patients. RNA sequencing data including long non-coding RNAs (lncRNAs), messenger RNA (mRNAs) and microRNAs (miRNAs) of 141 HNSCC and 44 adjacent normal tissues were obtained from the TCGA. Differentially expressed genes were analyzed using the R package DESeq. GO terms and Kyoto Encyclopedia of Genes and Genomes (KEGG) pathway enrichment analyses were conducted. A competing endogenous RNAs (ceRNA) network was constructed. The most differentially expressed genes in the main ceRNA network were chosen for nasopharyngeal carcinoma (NPC) cell lines and NPEC2 Bmi-1 cell line verification. A receiver operating characteristic (ROC) curve was constructed for 141 specimens of HNSCC tissues from 44 control samples. In our study, 79 HNSCC-associated abnormally expressed lncRNAs , 86 abnormally expressed miRNAs and 324 abnormally expressed mRNAs were identified. The public microarray results showed that LINC00958 and HOXC13-AS expression levels were upregulated in HNSCC tissues compared with the adjacent normal tissues in this study (p < 0.0001). LINC00958 and HOXC13-AS expression levels in NPC cell lines were higher than those in the NPEC2 Bmi-1 cell line (p < 0.05). The results showed that the area under the ROC curve (AUC) of LINC00958 reached up to 0.906 at a cutoff value of 7.96, with a sensitivity and specificity of 80.85% and 90.91%, respectively. The AUC of HOXC13-AS reached up to 0.898 at a cutoff value of 0.695, with sensitivity and specificity values of 86.23% and 83.78%, respectively. The current study indicates that LINC00958 and HOXC13-AS are new candidate diagnostic biomarkers for HNSCC patients. ©2020 Xiong et al.