Hepatocellular carcinoma (HCC) is well known of poor prognosis and short survival owing to high recurrence rate even after curative surgery. Today there is no available biomarker or biochemical test to indicate HCC recurrence, and this study aims to identify protein markers that can discriminate post-operative patients with early recurrence (ER), disease relapsed within the first year. In this study, 103 hepatitis B-related HCC patients were recruited and 68 of them were used for ER-related biomarker discovery study. Proteomic expression patterns of matched tumor and adjacent non-tumor tissues from these patients plus 16 normal liver tissues were delineated by 2-DE differential profiling method. Significant protein spots were evaluated by hierarchical clustering analysis. SSP4612 that yielded the highest ROC curve value for the ER subgroup of HCC was subsequently identified by tandem mass spectrometry, and the corresponding expression patterns were further confirmed by quantitative PCR, western blot and immunohistochemistry. Correlation analysis with clinicopathological data was also examined. Proteomic profiling analysis revealed overexpression of mortalin (gene HSPA9) in HCC when compared to the non-tumor and normal liver tissues (AUC=0.821). Furthermore, elevated mortalin level was also detected in the ER subgroup of HCC versus the recurrence free (RF) state (where no cancer recurs for >1 year) (AUC=0.833, sensitivity=90.9% and specificity=71.4%). Metastatic HCC cell lines also exhibited higher levels of mortalin and HSPA9 mRNA. Clinically, mortalin overexpression in HCC was closely associated with advanced tumor stages and venous infiltration, having implications for increased malignancy and aggressive behavior. Mortalin (HSPA9) is associated with HCC metastasis and thus suggested as a tumor marker for predicting early recurrence, which may have immediate clinical applications for cancer surveillance after curative surgery.