Despite significant advances in the detection and treatment of hepatocellular carcinoma, the prognosis of patients with hepatocellular carcinoma remains very poor, in part due to the high incidence of recurrence. This study was aimed at identifying a prognostic indicator of recurrence in patients with hepatocellular carcinoma. We retrospectively analyzed CpG island hypermethylation of the p14, p15, p16, GSTP1, integrin alpha4, SYK, and CDH1 genes in fresh-frozen tissues from 265 patients with hepatocellular carcinoma using the methylation-specific PCR. The expression levels of p16 and p53 were evaluated by immunohistochemistry. CpG island hypermethylation was detected in 6% for p14, 21% for p15, 67% for p16, 75% for GSTP1, 23% for integrin alpha4, 12% for SYK, and 57% for CDH1. Recurrence was observed in 102 (38%) of the 265 patients. There was no association between the risk for recurrence and hypermethylation of any gene studied. However, p16 methylation was associated with a poor survival after surgery for recurrent stage I to II hepatocellular carcinomas (hazard ratio, 4.05; 95% confidence interval, 1.15-14.20; P = 0.03). In addition, the hazard of failure after recurrence was about 3.80 (95% confidence interval, 1.03-14.20; P = 0.04) times higher in patients with p16 methylation than in those without. Negative expression of p16 at a protein level was also associated with poor survival in recurrent stage I to II hepatocellular carcinomas, but p53 expression did not have a synergistic effect on the poor prognosis. In conclusion, the present study suggests that p16 methylation may be associated with a poor prognosis in recurrent early-stage hepatocellular carcinomas.