Early detection improves hepatocellular carcinoma (HCC) outcomes, but better noninvasive surveillance tools are needed. We aimed to identify and validate methylated DNA markers (MDMs) for HCC detection. Reduced representation bisulfite sequencing was performed on DNA extracted from 18 HCC and 35 control tissues. Candidate MDMs were confirmed by quantitative methylation-specific PCR in DNA from independent tissues (74 HCC, 29 controls). A phase I plasma pilot incorporated quantitative allele-specific real-time target and signal amplification assays on independent plasma-extracted DNA from 21 HCC cases and 30 controls with cirrhosis. A phase II plasma study was then performed in 95 HCC cases, 51 controls with cirrhosis, and 98 healthy controls using target enrichment long-probe quantitative amplified signal (TELQAS) assays. Recursive partitioning identified best MDM combinations. The entire MDM panel was statistically cross-validated by randomly splitting the data 2:1 for training and testing. Random forest (rForest) regression models performed on the training set predicted disease status in the testing set; median areas under the receiver operating characteristics curve (AUCs; and 95% confidence interval [CI]) were reported after 500 iterations. In phase II, a six-marker MDM panel (homeobox A1 [HOXA1], empty spiracles homeobox 1 [EMX1], AK055957, endothelin-converting enzyme 1 [ECE1], phosphofructokinase [PFKP], and C-type lectin domain containing 11A [CLEC11A]) normalized by beta-1,3-galactosyltransferase 6 (B3GALT6) level yielded a best-fit AUC of 0.96 (95% CI, 0.93-0.99) with HCC sensitivity of 95% (88%-98%) at specificity of 92% (86%-96%). The panel detected 3 of 4 (75%) stage 0, 39 of 42 (93%) stage A, 13 of 14 (93%) stage B, 28 of 28 (100%) stage C, and 7 of 7 (100%) stage D HCCs. The AUC value for alpha-fetoprotein (AFP) was 0.80 (0.74-0.87) compared to 0.94 (0.9-0.97) for the cross-validated MDM panel (P < 0.0001). Conclusion: MDMs identified in this study proved to accurately detect HCC by plasma testing. Further optimization and clinical testing of this promising approach are indicated.