Purpose Non–small-cell lung cancer (NSCLC) is a tumor in which only small improvements in clinical outcome have been achieved. The issue is critical for stage I patients for whom there are no available biomarkers that indicate which high-risk patients should receive adjuvant chemotherapy. We aimed to find DNA methylation markers that could be helpful in this regard. Patients and Methods A DNA methylation microarray that analyzes 450,000 CpG sites was used to study tumoral DNA obtained from 444 patients with NSCLC that included 237 stage I tumors. The prognostic DNA methylation markers were validated by a single-methylation pyrosequencing assay in an independent cohort of 143 patients with stage I NSCLC. Results Unsupervised clustering of the 10,000 most variable DNA methylation sites in the discovery cohort identified patients with high-risk stage I NSCLC who had shorter relapse-free survival (RFS; hazard ratio [HR], 2.35; 95% CI, 1.29 to 4.28; P = .004). The study in the validation cohort of the significant methylated sites from the discovery cohort found that hypermethylation of five genes was significantly associated with shorter RFS in stage I NSCLC: HIST1H4F, PCDHGB6, NPBWR1, ALX1, and HOXA9. A signature based on the number of hypermethylated events distinguished patients with high- and low-risk stage I NSCLC (HR, 3.24; 95% CI, 1.61 to 6.54; P = .001). Conclusion The DNA methylation signature of NSCLC affects the outcome of stage I patients, and it can be practically determined by user-friendly polymerase chain reaction assays. The analysis of the best DNA methylation biomarkers improved prognostic accuracy beyond standard staging.