The purpose of this study was to assess the value of cytokeratin 19 (CK19) and matrix metalloproteinase 2 (MMP-2) in predicting lymph node metastasis (LNM) and survival after curative resection in hepatocellular carcinoma (HCC) patients. Expression of CK19 and MMP-2 in tumor tissue was assessed through immunohistochemical staining of tissue microarrays (TMAs), which were constructed using samples from HCC patients with (n = 123) and without (n = 145) LNM. Positive CK19 expression was correlated with LNM (P < 0.001), satellite lesions (P = 0.016), and lymph node location (P = 0.039). High MMP-2 expression correlated with LNM (P < 0.001), UICC T stage (P = 0.023), and Edmondson grade (P = 0.022). Moreover, CK19 expression correlated with MMP-2 expression (P = 0.033). CK19 and MMP-2 expression were predictive of HCC LNM (AUC: 0.640; 95% CI: 0.572-0.707; P < 0.001 and AUC: 0.611; 95% CI: 0.544-0.679; P = 0.002, respectively). CK19 and MMP-2 expression were independent prognostic factors for disease-free survival (P = 0.031 and P = 0.012, respectively) and overall survival (P = 0.013 and P = 0.018, respectively) in HCC patients with LNM. CK19 expression (P < 0.001), MMP-2 expression (P = 0.006), and UICC T stage (P < 0.001) were independent risk factors for developing LNM in HCC. These findings show that CK19 and MMP-2 expression may be beneficial in predicting HCC LNM and survival.