A genome-wide study using expression profiles of 12,600 genes was conducted to identify methylated genes that could be used for early diagnosis of hepatocellular carcinoma (HCC). Of the 12,600 genes examined, we identified 23 genes with significantly lower expression levels in HCC tissues than in non-HCC liver tissues by our statistical and CpG mapping tests. Of these 23 genes, methylation analysis by direct sequencing with bisulfite treatment determined 4 genes that were aberrantly methylated in 20 HCC samples of TNM stages I and II. Further methylation analysis of the 4 genes by quantitative sequencing with 20 HCCs and the corresponding non-tumor liver tissues from an independent cohort of HCC patients revealed that 2 genes, BASP1 and SRD5A2, were aberrantly methylated in only HCC tissues, though not in any corresponding non-tumor liver tissues. Notably, in the cohort we found that BASP1 or SRD5A2 were aberrantly methylated when a cut-off value of 30% in the methylation rate was used, in all cases of 11 HCCs of TNM stages I and II, of 10 well-differentiated HCCs and of 4 small HCCs <2 cm in maximum diameter, but in none of the 20 corresponding non-HCC livers. Methylation-specific PCR for BASP1 and SRD5A2 reproduced the same results observed by direct sequencing. These results indicate that BASP1 and SRD5A2 might serve as useful biomarkers for early diagnosis of HCC.