The mechanism of early recurrence of hepato-cellular carcinoma (HCC) is not well understood. To examine whether early intrahepatic metastasis of HCC can be determined by the reliable molecular characteristics of the primary HCC, we focused on early-stage tumors of primary and solitary HCC cases. Proteomic differences were investigated between two groups, 11 early (recurrence within 12 months) and 10 late (no recurrence within 48 months) HCC cases, using two-dimensional fluorescence difference gel electrophoresis. Overall, 10 upregulated and 9 downregulated proteins were identified from a total of 1623 protein spots detected in early recurrent HCC. Cluster analysis using the 19 proteins successfully divided the 21 HCC samples exactly into the two above groups. A multifunctional protein, transglutaminase 2 (TGM2), was upregulated in the early recurrence group. Immunohistochemistry revealed the frequent observation of TGM2-positive HCC cells in the early group, with a tendency of TGM2-positive staining in HCC cells adjacent to fibrous stroma. To examine whether two major TGM2-associated pathways, epithelial-mesenchymal transition (EMT) and integrin signaling, were activated in the early recurrence group of HCC, downstream molecules of TGM2 were measured. The mRNA level of EMT-related genes was highly positively correlated with TGM2 mRNA. However, E-cadherin (CDH1) mRNA and protein were not downregulated in correlation with TGM2 expression. The phosphorylation of FAK and Akt and the downregulation of PTEN were not associated with the quantity of TGM2. Therefore, TGM2 might contribute to early HCC recurrence through signaling pathways not related to EMT and integrin signaling. The proteomics of strictly classified HCCs would be useful for characterizing pro-metastatic HCC and for developing a new therapeutic target for treatment of metastasis.