Epigenetic studies on the role of DNA-modifying enzymes in HNSCC tumorigenesis have focused on a single enzyme or a group of enzymes. To acquire a more comprehensive insight into the expression profile of methyltransferases and demethylases, in the present study, we examined the mRNA expression of the DNA methyltransferases DNMT1, DNMT3A, and DNMT3B, the DNA demethylases TET1, TET2, TET3, and TDG, and the RNA methyltransferase TRDMT1 by RT-qPCR in paired tumor–normal tissue samples from HNSCC patients. We characterized their expression patterns in relation to regional lymph node metastasis, invasion, HPV16 infection, and CpG73 methylation. Here, we show that tumors with regional lymph node metastases (pN+) exhibited decreased expression of DNMT1, 3A and 3B, and TET1 and 3 compared to non-metastatic tumors (pN0), suggesting that metastasis requires a distinct expression profile of DNA methyltransferases/demethylases in solid tumors. Furthermore, we identified the effect of perivascular invasion and HPV16 on DNMT3B expression in HNSCC. Finally, the expression of TET2 and TDG was inversely correlated with the hypermethylation of CpG73, which has previously been associated with poorer survival in HNSCC. Our study further confirms the importance of DNA methyltransferases and demethylases as potential prognostic biomarkers as well as molecular therapeutic targets for HNSCC.