For practical reasons, in many studies PD-L1 expression is measured by combined positive score (CPS) from a single tumor sample. This does not reflect the heterogeneity of PD-L1 expression in head and neck squamous cell carcinoma (HNSCC). We investigated the extent and relevance of PD-L1 expression heterogeneity in HNSCC analyzing primary tumors and recurrences (LRs), as well as metastases. Tumor tissue from 200 HNSCC patients was immunohistochemically stained for PD-L1 and analyzed using image-analysis software QuPath v3.4 with multiple specimens per patient. CPS was ≥20 in 25.6% of primary tumors. Intra-tumoral heterogeneity led to a therapeutically relevant underestimation of PD-L1 expression in 28.7% of patients, when only one specimen per patient was analyzed. Inter-tumoral differences in PD-L1 expression between primary tumors and lymph node metastasis (LNM) or LR occurred in 44.4% and 61.5% (CPS) and in 40.6% and 50% of cases (TPS). Overall survival was increased in patients with CPS ≥ 1 vs. CPS < 1 in primary tumors and LNM (hazard ratio: 0.46 and 0.35; p < 0.005); CPS in LR was not prognostic. Our analysis shows clinically relevant intra- and inter-sample heterogeneity of PD-L1 expression in HNSCC. To account for heterogeneity and improve patient selection for immunotherapy, multiple sample analyses should be performed, particularly in patients with CPS/TPS < 1.