Lung cancer remains the leading cause of cancer death worldwide. Overall 5-year survival is ∼10–15% and despite curative intent surgery, treatment failure is primarily due to recurrent disease. Conventional prognostic markers are unable to determine which patients with completely resected disease within each stage group are likely to relapse. To identify a gene signature associated with recurrent squamous cell carcinoma (SCC) of lung, we analyzed primary tumor gene expression for a total of 51 SCCs (Stages I–III) on 22 323 element microarrays, comparing expression profiles for individuals who remained disease-free for a minimum of 36 months with those from individuals whose disease recurred within 18 months of complete resection. Cox proportional hazards modeling with leave-one-out cross-validation identified a 71-gene signature capable of predicting the likelihood of tumor recurrence and a 79-gene signature predictive for cancer-related death. These two signatures were pooled to generate a 111-gene signature which achieved an overall predictive accuracy for disease recurrence of 72% (77% sensitivity, 67% specificity) in an independent set of 58 (Stages I–III SCCs). This signature also predicted differences in survival [log-rank P=0.0008; hazard ratio (HR), 3.8; 95% confidence interval (CI), 1.6–8.7], and was superior to conventional prognostic markers such as TNM stage or N stage in predicting patient outcome. Genome-wide profiling has revealed a distinct gene-expression profile for recurrent lung SCC which may be clinically useful as a prognostic tool.