Aberrant DNA methylation has been implicated in the development of hepatocellular carcinoma (HCC). Our aim was to clarify its molecular mechanism and to identify useful biomarkers by screening for DNA methylation in HCC. Methylated CpG island amplification coupled with CpG island microarray (MCAM) analysis was carried out to screen for methylated genes in primary HCC specimens [hepatitis B virus (HBV)-positive, n = 4; hepatitis C virus (HCV)-positive, n = 5; HBV/HCV-negative, n = 7]. Bisulfite pyrosequencing was used to analyze the methylation of selected genes and long interspersed nuclear element (LINE)-1 in HCC tissue (n = 57) and noncancerous liver tissue (n = 50) from HCC patients and in HCC cell lines (n = 10). MCAM analysis identified 332, 342, and 259 genes that were methylated in HBV-positive, HCV-positive, and HBV/HCV-negative HCC tissues, respectively. Among these genes, methylation of KLHL35, PAX5, PENK, and SPDYA was significantly higher in HCC tissue than in noncancerous liver tissue, irrespective of the hepatitis virus status. LINE-1 hypomethylation was also prevalent in HCC and correlated positively with KLHL35 and SPDYA methylation. Receiver operating characteristic curve analysis revealed that methylation of the four genes and LINE-1 strongly discriminated between HCC tissue and noncancerous liver tissue. Our data suggest that aberrant hyper- and hypomethylation may contribute to a common pathogenesis mechanism in HCC. Hypermethylation of KLHL35, PAX, PENK, and SDPYA and hypomethylation of LINE-1 could be useful biomarkers for the detection of HCC.