Hepatocellular carcinoma (HCC) is one of the leading causes of mortality related to cancer all over the world. The poor prognosis of HCC is mostly due to recurrence and tumor metastasis. In order to better understand the molecular mechanisms of HCC metastasis, we analyzed the proteome of three HCC cell lines with different metastasis potentials by using quantitative proteomics and bioinformatics analysis. As a result, we identified 331 cellular proteins potentially associated to HCC metastasis, and constructed a highly connected protein-protein interaction (PPI) network. Functional annotation of the network uncovered prominent pathways and key roles of these proteins, suggesting that metabolism and cytoskeleton biological progresses are greatly involved with HCC metastasis. Furthermore, integrative network analysis revealed a rich-club organization in the PPI network indicating a hub center of connections, including several well-known cancer related proteins, such as SRC proto-oncogene, non-receptor tyrosine kinase (SRC) and pyruvate kinase M2 (PKM2). Moreover, the differential expressions of two identified proteins, including PKM2 and actin-related protein 2/3 complex subunit 4 (ARPC4), were validated using Western blotting. These two proteins were identified as potential prognostic markers for HCC by using survival rate analysis.