Epigenetic deregulation has emerged as a driver in human malignancies. There is no clear understanding of the epigenetic alterations in hepatocellular carcinoma (HCC) and of the potential role of DNA methylation markers as prognostic biomarkers. Analysis of tumor tissue from 304 patients with HCC treated with surgical resection allowed us to generate a methylation-based prognostic signature using a training-validation scheme. Methylome profiling was done with the Illumina HumanMethylation450 array (Illumina, Inc., San Diego, CA), which covers 96% of known cytosine-phosphate-guanine (CpG) islands and 485,000 CpG, and transcriptome profiling was performed with Affymetrix Human Genome U219 Plate (Affymetrix, Inc., Santa Clara, CA) and miRNA Chip 2.0. Random survival forests enabled us to generate a methylation signature based on 36 methylation probes. We computed a risk score of mortality for each individual that accurately discriminated patient survival both in the training (221 patients; 47% hepatitis C-related HCC) and validation sets (n = 83; 47% alcohol-related HCC). This signature correlated with known predictors of poor outcome and retained independent prognostic capacity of survival along with multinodularity and platelet count. The subset of patients identified by this signature was enriched in the molecular subclass of proliferation with progenitor cell features. The study confirmed a high prevalence of genes known to be deregulated by aberrant methylation in HCC (e.g., Ras association [RalGDS/AF-6] domain family member 1, insulin-like growth factor 2, and adenomatous polyposis coli) and other solid tumors (e.g., NOTCH3) and describes potential candidate epidrivers (e.g., septin 9 and ephrin B2). Conclusions: A validated signature of 36 DNA methylation markers accurately predicts poor survival in patients with HCC. Patients with this methylation profile harbor messenger RNA-based signatures indicating tumors with progenitor cell features.