Approximately 20% of head and neck squamous cell carcinomas (HNSCC) exhibit reduced methylation on lysine 36 of histone H3 (H3K36me) due to mutations in histone methylase NSD1 or a lysine-to-methionine mutation in histone H3 (H3K36M). Whether such alterations of H3K36me can be exploited for therapeutic interventions is still unknown. Here, we show that HNSCC models expressing H3K36M can be divided into two groups: those that display aberrant accumulation of H3K27me3 and those that maintain steady levels of H3K27me3. The first group shows decreased proliferation, genome instability, and increased sensitivity to genotoxic agents, such as PARP1/2 inhibitors. In contrast, the H3K36M HNSCC models with steady H3K27me3 levels do not exhibit these characteristics unless H3K27me3 levels are elevated, either by DNA hypomethylating agents or by inhibiting the H3K27me3 demethylases KDM6A/B. Mechanistically, we found that H3K36M reduces H3K36me by directly impeding the activities of the histone methyltransferase NSD3 and the histone demethylase LSD2. Notably, we found that aberrant H3K27me3 levels induced by H3K36M expression is not a bona fide epigenetic mark in HNSCC since it requires continuous expression of H3K36M to be inherited. Moreover, increased sensitivity of H3K36M HNSCC models to PARP1/2 inhibitors solely depends on the increased H3K27me3 levels. Indeed, aberrantly high H3K27me3 levels decrease BRCA1 and FANCD2-dependent DNA repair, resulting in higher sensitivity to DNA breaks and replication stress. Finally, in support of our in vitro findings, a PARP1/2 inhibitor alone reduce tumor burden in a H3K36M HNSCC xenograft model with elevated H3K27me3, whereas in a H3K36M HNSCC xenograft model with consistent H3K27me3 levels, a combination of PARP1/2 inhibitors and agents that upregulate H3K27me3 proves to be successful. In conclusion, our findings underscore a delicate balance between H3K36 and H3K27 methylation, essential for maintaining genome stability. This equilibrium presents promising therapeutic opportunities for patients with H3K36me-deficient tumors.