Background: Hepatocellular carcinoma (HCC) represents the second most common cause of cancer deaths worldwide. □-fetoprotein (AFP) is the most common serological test used for screening and diagnosis of HCC. However, it is widely recognized that AFP has lower sensitivity with sub-optimal specificity. Tumor-originated circulating cell-free DNA (cfDNA) provides new opportunity for non-invasive detection of liver cancer. Methods: HCC-specific differentially methylated regions (DMRs) were identified by whole genome bisulfite sequencing (WGBS) in 44 pairs of HCC tissues and adjacent tissues. We then performed methylome profiling on cfDNA from HCC patients and healthy individuals by targeted bisulfite sequencing covering genome-wide CpG islands, shelves, and shores. We employed machine learning approaches to build diagnostic models based on cfDNA regional methylation level to classify the plasma of HCC (n = 140) from that of healthy individuals (n = 84). Further analyses were performed in the validation cohort, including 155 HCC patients, and a control group with 96 healthy individuals, 21 chronic hepatitis B infection (CHB)/liver cirrhosis (LC) patients and 34 patients with benign hepatic lesions (BHL). Area under the receiver operating characteristic curve (AUC-ROC) was used to evaluate diagnostic performance. Results: A random forest classifier achieved an AUC of 0.97 (sensitivity: 92.9%; specificity: 89.4%) with 10-fold cross-validation using a panel of 39 DMR markers. The AUC of the diagnostic panel was 0.93 (sensitivity: 81.3%; specificity: 90.7%) in validation cohort, and it performed equally well in detecting BCLC stage 0+A (AUC = 0.90; sensitivity: 74.7%) and AFP negative (AUC = 0.92; sensitivity: 79.4%) HCC, as well as differentiating HCC from CHB/LC and BHL. Based on these results, we have further developed a small targeted bisulfite sequencing panel covering 127 CpG sites for non-invasive diagnosis of HCC. The panel had similar performance in training and validation cohorts, an AUC of 0.96 (sensitivity: 90.7%, specificity: 88.2%) in the training set, and 0.91 (sensitivity: 80.0%, specificity: 88.7%) in the validation set. Conclusions: Our diagnostic panel with 39 DMR markers showed high sensitivity and specificity in HCC diagnosis as well as surveillance in high-risk populations for developing HCC. More importantly, simple diagnostic model show similar diagnostic performance for early HCC diagnosis, which was easily to transfer to clinical application in the future.