Histological differentiation is a major pathological criterion indicating the risk of tumor invasion and metastasis in patients with hepatocellular carcinoma. The degree of tumor differentiation is controlled by a complex interacting network of associated proteins. The principal aim of the present study is to identify the possible differentiation-related proteins which may be used for early diagnosis and more effective therapies. We compared poorly differentiated and well-differentiated hepatocellular carcinoma tissues by using 2-dimensional gel electrophoresis and matrix-assisted laser desorption ionization time-of-flight mass spectrometry. Among the 11 identified protein spots, 6 were found to be upregulated in poorly differentiated hepatocellular carcinoma tissues and 5 were correspondingly downregulated. Immunohistochemistry was performed on 106 hepatocellular carcinoma tissues to confirm the results of the proteomic analysis. By using bioinformatic tools GO and STRING, these proteins were found to be related to catalytic activity, binding, and antioxidant activity. In particular, our data suggest that overexpression of peroxiredoxin-2, annexin A2, and heat shock protein β-1 was correlated with tumor invasion, metastasis, and poor prognosis, and therefore, these proteins may serve as potential diagnostic and therapeutic biomarkers.