Distant metastases (DM) in head and neck squamous cell carcinoma (HNSCC) remain a challenge as treatment options are limited. To identify biomarkers predictive of DM in primary tumors (PT), gene expression profiling was performed in PT from patients who did, or did not develop DM (T-with and T-without, n = 25 and 24, respectively), and in matched DM. A total of 185 and 42 differentially expressed genes were identified in the T-with vs. T-without and the T-with vs. DM comparisons, respectively. The intersection between these two comparisons identified COX7A1 and TBX5 as common genes. In three independent datasets, both genes were able to significantly distinguish patients according to their DM-free survival. By functional biological analyses, the T-without group showed enrichment in immune-response pathways, whereas the T-with group showed an enrichment in B-plasma cells and Tregs. Increased enrichment of proliferation-related pathways was observed in the T-with group compared with that in the DM group. Further comparisons with/without DM are needed to confirm these data in order to improve clinical management of HNSCC.