Hepatocellular carcinoma (HCC) is an aggressive liver cancer but clinically validated biomarkers that can predict natural history of malignant progression are lacking. The present study explored the proteome-wide patterns of HCC to identify biomarker signature that could distinguish cancerous and nonmalignant liver tissues. A retrospective cohort of 80 HBV-associated HCC was included and both the tumor and adjacent nontumor tissues were subjected to proteome-wide expression profiling by 2-DE method. The subjects were randomly divided into the training (n = 55) and validation (n = 25) subsets, and the data analyzed by classification-and-regression tree algorithm. Protein markers were characterized by MALDI-ToF/MS and confirmed by immunohistochemistry, Western blotting and qPCR assays. Proteomic expression signature composed of six biomarkers (haptoglobin, cytochrome b5, progesterone receptor membrane component 1, heat shock 27 kDa protein 1, lysosomal proteinase cathepsin B, keratin I) was developed as a classifier model for predicting HCC. We further evaluated the model using both leave-one-out procedure and independent validation, and the overall sensitivity and specificity for HCC both are 92.5%, respectively. Clinical correlation analysis revealed that these biomarkers were significantly associated with serum AFP, total protein levels and the Ishak's score. The described model using biomarker signatures could accurately distinguish HCC from nonmalignant tissues, which may also provide hints on how normal hepatocytes are transformed to malignant state during tumor progression.