Deciphering the network of signaling pathways in cancer via protein-protein interactions (PPIs) at the cellular level is a promising approach but remains incomplete. We used an in situ proximity ligation assay to identify and quantify 67 endogenous PPIs among 21 interlinked pathways in two hepatocellular carcinoma (HCC) cells, Huh7 (minimally migratory cells) and Mahlavu (highly migratory cells). We then applied a differential network biology analysis and determined that the novel interaction, CRKL-FLT1, has a high centrality ranking, and the expression of this interaction is strongly correlated with the migratory ability of HCC and other cancer cell lines. Knockdown of CRKL and FLT1 in HCC cells leads to a decrease in cell migration via ERK signaling and the epithelial-mesenchymal transition process. Our immunohistochemical analysis shows high expression levels of the CRKL and CRKL-FLT1 pair that strongly correlate with reduced disease-free and overall survival in HCC patient samples, and a multivariate analysis further established CRKL and the CRKL-FLT1 as novel prognosis markers. This study demonstrated that functional exploration of a disease network with interlinked pathways via PPIs can be used to discover novel biomarkers.