There is increasing evidence that the spatial organization of cells within the tumor-immune microenvironment (TiME) of solid tumors influences survival and response to therapy in numerous cancer types. Here, we report results and demonstrate the applicability of quantitative single-cell spatial proteomics analyses in the TiME of primary and recurrent human papillomavirus (HPV)-negative head and neck squamous cell carcinoma (HNSCC) tumors. Single-cell compositions of a nine patient, primary and recurrent (n = 18), HNSCC cohort is presented, followed by deeper investigation into the spatial architecture of the TiME and its relationship with clinical variables and progression free survival (PFS). Multiple spatial algorithms were used to quantify the spatial landscapes of immune cells within TiMEs and demonstrate that neoplastic tumor-immune cell spatial compartmentalization, rather than mixing, is associated with longer PFS. Mesenchymal (αSMA+) cellular neighborhoods describe distinct immune landscapes associated with neoplastic tumor-immune compartmentalization and improved patient outcomes. Results from this investigation are concordant with studies in other tumor types, suggesting that trends in TiME cellular heterogeneity and spatial organization may be shared across cancers and may provide prognostic value in multiple cancer types.