Liver resection is a curative treatment for hepatocellular carcinoma (HCC). Tumor-infiltrating leukocytes (TILs) are important players in predicting HCC recurrence. However, the invasive margin could not be confirmed as relevant for HCC. The migration of immune cells into HCC may originate from intratumoral vessels. No previous study has examined perivascular (PV) infiltration. Tumors from 60 patients were examined. Immunohistochemistry was performed against CD3, CD8, CD20, and CD66b. TILs were counted in the PV regions using an algorithm for quantification of the tumor immune stroma (QTiS). The results were correlated with overall (OS) and disease-free survival (DFS), clinical parameters, and laboratory values. PV infiltration of TILs was predominant in resected HCC. Higher PV infiltration of CD3(+) (p = 0.016) and CD8(+) (p = 0.028) independently predicted better OS and DFS, respectively. CD20(+) showed a trend towards better DFS (p = 0.076). Scoring of CD3(+), CD8(+), and CD20(+) independently predicted OS and DFS (p < 0.01). The amount of perivascular-infiltrating CD3(+) cells is an independent predictor of better OS, and CD8(+) cells independently predict prolonged DFS. Our novel perivascular infiltration scoring (PVIS) can independently predict both DFS and OS in resected HCC patients.