Despite optimal and early surgical treatment of non-small-cell lung cancer (NSCLC), many patients die of recurrent NSCLC. We investigated the association between gene methylation and recurrence of the tumor.Fifty-one patients with stage I NSCLC who underwent curative resection but who had a recurrence within 40 months after resection (case patients) were matched on the basis of age, NSCLC stage, sex, and date of surgery to 116 patients with stage I NSCLC who underwent curative resection but who did not have a recurrence within 40 months after resection (controls). We investigated whether the methylation of seven genes in tumor and lymph nodes was associated with tumor recurrence.In a multivariate model, promoter methylation of the cyclin-dependent kinase inhibitor 2A gene p16, the H-cadherin gene CDH13, the Ras association domain family 1 gene RASSF1A, and the adenomatous polyposis coli gene APC in tumors and in histologically tumor-negative lymph nodes was associated with tumor recurrence, independently of NSCLC stage, age, sex, race, smoking history, and histologic characteristics of the tumor. Methylation of the promoter regions of p16 and CDH13 in both tumor and mediastinal lymph nodes was associated with an odds ratio of recurrent cancer of 15.50 in the original cohort and an odds ratio of 25.25 when the original cohort was combined with an independent validation cohort of 20 patients with stage I NSCLC.Methylation of the promoter region of the four genes in patients with stage I NSCLC treated with curative intent by means of surgery is associated with early recurrence.