The role of oral microbiota in head and neck squamous cell carcinoma (HNSCC) is poorly understood. Here we sought to evaluate the association of the bacterial microbiome with host gene methylation and patient outcomes, and to explore its potential as a biomarker for early detection or intervention. Here we performed 16S rRNA gene amplicon sequencing in sixty-eight HNSCC patients across both tissue and oral rinse samples to identify oral bacteria with differential abundance between HNSCC and controls. A subset of thirty-one pairs of HNSCC tumor tissues and the adjacent normal tissues were characterized for host gene methylation profile using bisulfite capture sequencing. We observed significant enrichments of Fusobacterium and Peptostreptococcus in HNSCC tumor tissues when compared to the adjacent normal tissues, and in HNSCC oral rinses when compared to healthy subjects, while ten other bacterial genera were largely depleted. These HNSCC-related bacteria were discriminative for HNSCC and controls with area under the receiver operating curves (AUCs) of 0.84 and 0.86 in tissue and oral rinse samples, respectively. Moreover, Fusobacterium nucleatum abundance in HNSCC cases was strongly associated with non-smokers, lower tumor stage, lower rate of recurrence, and improved disease-specific survival. An integrative analysis identified that enrichment of F. nucleatum was associated with host gene promoter methylation, including hypermethylation of tumor suppressor genes LXN and SMARCA2, for which gene expressions were downregulated in the HNSCC cohort from The Cancer Genome Atlas. In conclusion, we identified a taxonomically defined microbial consortium associated with HNSCC that may have clinical potential regarding biomarkers for early detection or intervention. Host–microbe interactions between F. nucleatum enrichment and clinical outcomes or host gene methylation imply a potential role of F. nucleatum as a pro-inflammatory driver in initiating HNSCC without traditional risk factors, which warrants further investigation for the underlying mechanisms.