To determine the methylation profile of multiple tumor-related genes during multistep hepatocarcinogenesis, we investigated the methylation status of CpG islands of 9 genes, using methylation-specific polymerase chain reaction for 60 paired hepatocellular carcinoma (HCC) and non-HCC liver tissue samples, 22 dysplastic nodule (DN), 30 liver cirrhosis (LC), 34 chronic hepatitis (CH) and 20 normal liver samples. The methylation status of 9 genes was correlated to the clinicopathological findings of HCC patients. All HCC samples showed methylation of at least one gene, whereas it was shown in 72.7% of DN and 40% of LC, but was not shown in CH and normal liver samples (P < 0.001). The number of genes methylated showed a stepwise increase with the progression of stages (0 for normal liver and CH, 0.5 for LC, 1.5 for DN, and 3.7 for HCC (P < 0.001)). The genes frequently methylated in HCC were APC (81.7%), GSTP1 (76.7%), RASSF1A (66.7%), p16 (48.3%), COX-2 (35%), and E-cadherin (33.3%). COX-2, p16, RASSF1A, and TIMP-3 were not methylated in LC and CH from patients without concurrent HCC. Chronic liver diseases with concurrent HCC showed higher methylation frequencies of the tested genes, and a higher number of methylated genes than those without concurrent HCC. HCC patients with methylation of E-cadherin or GSTP1 showed poorer survival than those without (P = 0.034 and 0.043, respectively). In conclusion, our results indicated that CpG island methylation of tumor-related genes is an early and frequent event, and accumulates step-by-step during a multistep hepatocarcinogenesis. CpG island methylation of E-cadherin or GSTP1 might serve as a potential biomarker for prognostication of HCC patients.