Background: The aim of this study was to identify more accurate variables to improve prognostication of individual patients with colorectal liver metastases (CRLM). Clinicopathological characteristics only partly explain the large range in survival rates. Methods: MessengerRNA expression profiles of resected CRLM of two patient groups were analysed by mRNA sequencing: poor survivors (death from recurrent disease <30 months after surgery) and good survivors (no recurrent disease >60 months after surgery). Tumour and adjacent liver parenchyma samples were analysed. Results: MessengerRNA expression profiling of the tumour samples identified 77 genes that were differentially expressed between the two survival groups at a False Discovery Rate (FDR) <0.1. In the adjacent liver parenchyma samples only one gene, MTRNR2L1, showed significantly higher expression in the good survivors. Pathway analysis showed higher expression of immune-related and stroma-related genes in tumour samples from good survivors. Expression data was then validated by immunohistochemistry in two cohorts comprising a total of 125 patients. Immunohistochemical markers that showed to be associated with good survival in the total cohort were: high K/L+ infiltration in tumour stroma [p = 0.029; OR 2.500 (95% CI 1.100–5.682)] and high CD79A+ infiltration in tumour stroma [p = 0.036; OR 2.428 (95%CI 1.062–5.552)]. Conclusions: A high stromal infiltration of CD79A+ B cells and K/L+ plasma cells might be favourable prognostic biomarkers after surgery for CRLM.