Complexities in cell-type composition have rightfully led to skepticism and caution in the interpretation of bulk transcriptomic analyses. Recent studies have shown that deconvolution algorithms can be utilized to computationally estimate cell-type proportions from the gene expression data of bulk blood samples, but their performance when applied to tumor tissues, including those from head and neck, remains poorly characterized. Here, we use single-cell data (~6000 single cells) collected from 21 head and neck squamous cell carcinoma (HNSCC) samples to generate cell-type-specific gene expression signatures. We leverage bulk RNA-seq data from >500 HNSCC samples profiled by The Cancer Genome Atlas (TCGA), and using single-cell data as a reference, apply two newly developed deconvolution algorithms (CIBERSORTx and MuSiC) to the bulk transcriptome data to quantitatively estimate cell-type proportions for each tumor in TCGA. We show that these two algorithms produce similar estimates of constituent/major cell-type proportions and that a high T-cell fraction correlates with improved survival. By further characterizing T-cell subpopulations, we identify that regulatory T-cells (Tregs) were the major contributor to this improved survival. Lastly, we assessed gene expression, specifically in the Treg population, and found that TNFRSF4 (Tumor Necrosis Factor Receptor Superfamily Member 4) was differentially expressed in the core Treg subpopulation. Moreover, higher TNFRSF4 expression was associated with greater survival, suggesting that TNFRSF4 could play a key role in mechanisms underlying the contribution of Treg in HNSCC outcomes.