Background: Immune checkpoint inhibitors are most beneficial in patients with high tumour PD-L1 expression. However, the use of PD-L1 expression is not straightforward. We investigated PD-L1 expression and immune cell (IC) infiltrates in non-small-cell lung cancer (NSCLC) patients treated with nivolumab. Methods: Tumour tissue specimens of 139 NSCLC patients were scored for tumour/stromal PD-L1 and various IC expression markers, and associated with durable clinical benefit (DCB) and overall survival (OS). Results: Median OS was higher for patients with high stromal infiltration of CD8+ ICs (9.0 months) compared with patients with low and intermediate infiltration (both 5.0 months, p = 0.035) and for patients with high infiltration of stromal CD4+ ICs (9.0 months) compared with patients with low and intermediate infiltration (both 5.0 months, p = 0.010) and this was confirmed in the validation cohort. Post hoc analyses showed that biopsies taken after the last line of chemotherapy (ACT) were predictive for DCB and OS, whereas samples obtained before the last line of chemotherapy (BCT) were not. Conclusions: Stromal infiltration of ICs can predict response to PD-1-directed immunotherapy in NSCLC patients. Interestingly, we found differences in the predictive value of IC markers between the ACT and BCT biopsies, suggesting that chemotherapy might influence the immune microenvironment.