Differentially methylated oral squamous cell carcinoma (OSCC) biomarkers, identified in vitro and validated in well-characterized surgical specimens, have shown poor clinical correlation in cohorts with different risk profiles. To overcome this lack of relevance, we used the HumanMethylation27 BeadChip, publicly available methylation and expression array data, and quantitative methylation specific PCR to uncover differential methylation in OSCC clinical samples with heterogeneous risk profiles. A two stage design consisting of discovery and prevalence screens was used to identify differential promoter methylation and deregulated pathways in patients diagnosed with OSCC and head and neck squamous cell carcinoma. Promoter methylation of KIF1A (κ = 0.64), HOXA9 (κ = 0.60), NID2 (κ = 0.60), and EDNRB (κ = 0.60) had a moderate to substantial agreement with clinical diagnosis in the discovery screen. HOXA9 had 68% sensitivity, 100% specificity, and a 0.81 Area Under the Curve (AUC). NID2 had 71% sensitivity, 100% specificity, and a 0.79 AUC. In the prevalence screen, HOXA9 (κ = 0.82) and NID2 (κ = 0.80) had an almost perfect agreement with histologic diagnosis. HOXA9 had 85% sensitivity, 97% specificity, and a 0.95 AUC. NID2 had 87% sensitivity, 95% specificity, and a 0.91 AUC. A HOXA9 and NID2 gene panel had 94% sensitivity, 97% specificity, and a 0.97 AUC. In saliva, from OSCC cases and controls, HOXA9 had 75% sensitivity, 53% specificity, and a 0.75 AUC. NID2 had 87% sensitivity, 21% specificity, and a 0.73 AUC. This phase I Biomarker Development Trial identified a panel of differentially methylated genes in normal and OSCC clinical samples from patients with heterogeneous risk profiles. This panel may be useful for early detection and cancer prevention studies.