Despite advances in the detection and treatment of lung cancer, the prognosis for patients with lung cancer is poor, partly as a result of recurrences. We retrospectively analyzed the relationship between recurrence and survival in patients with non-small cell lung cancers (NSCLC), and the promoter methylation of p16, GSTP1, FHIT, H-cadherin, and RARbeta2 genes to identify a prognostic molecular marker associated with the recurrence of NSCLC. Methylation status from 335 paraffin blocks was determined by methylation-specific PCR. Of the 335 NSCLC samples, promoter methylation was detected in 35% for p16, 39% for RARbeta2, 42% for H-cadherin, 7% for GSTP1, and 21% for FHIT. Recurrence was observed in 39% (132 of 335) of the patients. Recurrence was significantly associated with histology (P = 0.001) and pathologic stage (P = 0.009). Hypermethylation of any single gene was not associated with recurrence in patients. However, cohypermethylation of p16 and FHIT genes in stage I NSCLCs was associated with an increased risk of recurrence [odds ratio, 6.43; 95% confidence interval (CI), 1.04-20.19; P = 0.02] and poor recurrence-free survival after surgery (hazard ratio, 2.03; 95% CI, 1.09-6.23; P = 0.02). In addition, their survival after recurrence was also 4.62 times poorer (95% CI, 1.27-16.48; P = 0.005) than for those without cohypermethylation of both genes. In conclusion, the present study suggests that cohypermethylation of p16 and FHIT genes in patients with stage I NSCLC may be a valuable biomarker for predicting the recurrence-associated prognosis of the disease.