Nuclear factor, erythroid 2-like 2 (NFE2L2), a transcription factor also known as NF-E2-related factor 2 (Nrf2), is a key cytoprotective gene that regulates critical antioxidant and stress-responsive genes. Nrf2 has been demonstrated to be a promising therapeutic target and useful biomarker in malignant disease. We hypothesized that NFE2L2-mediated gene expression would reflect cancer severity and progression. We conducted a meta-analysis of microarray data for 240 NFE2L2-mediated genes that were enriched in tumor tissues. We then developed a risk scoring system based on NFE2L2 gene expression profiling and designated 50 tumor-associated genes as the NFE2L2-associated molecular signature (NAMS). We tested the relationship between this gene expression signature and both recurrence-free survival and overall survival in lung cancer patients. We find that NAMS predicts clinical outcome in the training cohort and in 12 out of 20 validation cohorts. Cox proportional hazard regressions indicate that NAMS is a robust prognostic gene signature, independent of other clinical and pathological factors including patient age, gender, smoking, gene alteration, MYC level, and cancer stage. NAMS is an excellent predictor of recurrence-free survival and overall survival in human lung cancer. This gene signature represents a promising prognostic biomarker in human lung cancer.