Aberrant DNA methylation represents an important issue in hepatocellular carcinoma (HCC). An innovative genome-wide DNA methylation analytical approach, based on the identification of Stochastic Epigenetic Mutations (SEMs) analysis, was undertaken to deeply evaluate DNA methylation alterations in HCC. Genome-wide methylation analysis has been performed in 69 pairs of HCC tumor and adjacent non-cancerous liver tissues using the Infinium HumanMethylation 450K BeadChip array. HCC and peritumoral tissues showed a different epigenetic profile, mainly characterized by loss of DNA methylation in HCC. Total number of SEMs was significantly higher in HCC tumor (median: 77,370) than in peritumoral (median: 5,656) tissues and correlated with tumor grade. A significant positive association emerged between SEMs measured in peritumoral tissue and hepatitis B and/or C virus infection status. A restricted number of SEMs resulted to be shared by more than 90% of tumor samples and never present in peritumoral tissue. This analysis allowed the identification of four epigenetically regulated candidate genes (AJAP1, ADARB2, PTPRN2, SDK1), potentially involved in the pathogenesis of HCC. In conclusion, HCC showed a methylation profile deregulated and very far from adjacent non-cancerous liver tissues. The SEM analysis provided valuable clues for further investigations in understanding the process of tumorigenesis in HCC.