Gene expression signatures generated from DNA microarray analyses have shown promise as predictive biomarkers of clinical outcome. In this study, we determined a high-risk signature for disease recurrence using formalin-fixed head and neck squamous cell carcinoma (HNSCC) tumors and compared the results with an independent data set obtained from fresh frozen tumors. We also showed that genes involved in epithelial-to-mesenchymal transition (EMT) and nuclear factor-kappaB (NF-kappaB) signaling deregulation are the most prominent molecular characteristics of the high-risk tumors. Gene expression was determined in 40 samples, including 34 formalin-fixed tissues and 6 matched frozen tissues, from 29 HNSCC patients. A 75-gene list predictive of disease recurrence was determined by training on the formalin-fixed tumor data set and tested on data from the independent frozen tumor set from 60 HNSCC patients. The difference in recurrence-free survival (RFS) between the high-risk versus low-risk groups in the training and test sets was statistically significant (P = 0.002 and 0.03, respectively, log-rank test). In addition, the gene expression data was interrogated using Gene Set Enrichment Analysis to determine biological significance. The most significant sets of genes enriched in the high-risk tumors were genes involving EMT, NF-kappaB activation, and cell adhesion. In conclusion, global gene expression analysis is feasible using formalin-fixed tissue. The 75-gene list can be used as a prognostic biomarker of recurrence, and our data suggest that the molecular determinants of EMT and NF-kappaB activation can be targeted as the novel therapy in the identified high-risk patients.