Head and Neck Squamous Cell Carcinomas (HNSCC) are the seventh most prevalent form of cancer and are associated with human papilloma virus infection (HPV-positive) or with tobacco and alcohol use (HPV-negative). HPV-negative HNSCCs have a high recurrence rate, and individual patients' responses to treatment vary greatly due to the high level of cellular heterogeneity of the tumor and its microenvironment. Here, we describe a HNSCC single cell atlas, which we created by integrating six publicly available datasets encompassing over 230,000 cells across 54 patients. We contextualized the relationships between existing signatures and cell populations, identified new subpopulations, and show the power of this large-scale resource to robustly identify associations between transcriptional signatures and clinical phenotypes that would not be possible to discover using fewer patients. We reveal a previously undefined myeloid population, sex-associated changes in cell type proportions, and novel interactions between CXCL8-positive fibroblasts and vascular endothelial cells. Beyond our findings, the atlas will serve as a public resource for the high-resolution characterization of tumor heterogeneity of HPV-negative HNSCC.