Cancer cells with a high glycolytic rate have an advantage in tumor growth. Hepatocellular carcinoma (HCC) often exhibits an aberrant expression of glycolytic enzymes, particularly type II hexokinase (HKII) and aldolase B (ALDOB). This study examined the aberrant expression of HKII and ALDOB in 203 surgically resected HCCs. A dramatic down-regulation of ALDOB was found in 116 HCCs (57%), while 43% of HCCs maintained the expression. HKII mRNA was overexpressed in 70 (35%) primary HCCs. The ALDOB down-regulation and HKII overexpression correlated with high-grade (grade II-IV) HCC (all ps<0.0001), portal vein invasion (stage IIIB-IV) (ps<1x10(-6)), early tumor recurrence (ETR) (p<0.001 and p<0.01, respectively) and a lower 5-year survival (p=0.000001 and p=0.0062, respectively). Notably, in stage II HCC which had no vascular invasion, the ALDOB down-regulation was associated with ETR (p<0.05) and a lower 5-year survival (p=0.015). The down-regulation of ALDOB correlated with a high AFP (p=1x10(-8)), whereas the overexpression of HKII, which has two functional motifs for the mutant p53, correlated with the p53 mutation, p<0.01. The three factors (ALDOB down-regulation, HKII overexpression and p53 mutation) not only correlated with tumor progression, but also interacted with one another, leading to a more aggressive HCC with a portal vein invasion and various extent of intrahepatic metastasis by more than four-fold (ps<1x10(-6)) and frequent ETR by more than two-fold (ps<0.0001) compared with HCCs without the events. In conclusion, the aberrant expression of ALDOB and HKII is associated with advanced disease, ETR and poor prognosis, and ALDOB down-regulation in stage II HCC is a predictive marker of ETR and an unfavorable outcome.