Panels of prognostic biomarkers selected using candidate approaches often do not validate in independent populations, so additional strategies are needed to identify reliable classifiers. In this study, we used an array-based approach to measure DNA methylation and applied a novel method for grouping CpG dinucleotides according to well-characterized genomic sequence features. A hypermethylation profile among 13 CpG loci, characterized by polycomb group target genes, mammalian interspersed repeats, and transcription factor-binding sites (PcG/MIR/TFBS), was associated with reduced survival (HR, 3.98; P = 0.001) in patients with head and neck squamous cell carcinoma. This association was driven by CpGs associated with the TAP1 and ALDH3A1 genes, findings that were validated in an independent patient group (HR, 2.86; P = 0.04). Together, the data not only elucidate new potential targets for therapeutic intervention in head and neck cancer but also may aid in the identification of poor prognosis patients who may require more aggressive treatment regimens.