Rap1GAP is a critical tumor suppressor gene that is downregulated in multiple aggressive cancers, such as head and neck squamous cell carcinoma, melanoma and pancreatic cancer. However, the mechanistic basis of rap1GAP downregulation in cancers is poorly understood. By employing an integrative approach, we demonstrate polycomb-mediated repression of rap1GAP that involves Enhancer of Zeste Homolog 2 (EZH2), a histone methyltransferase in head and neck cancers. We further demonstrate that the loss of miR-101 expression correlates with EZH2 upregulation, and the concomitant downregulation of rap1GAP in head and neck cancers. EZH2 represses rap1GAP by facilitating the trimethylation of histone 3 at lysine 27, a mark of gene repression, and also hypermethylation of rap1GAP promoter. These results provide a conceptual framework involving a microRNA-oncogene-tumor suppressor axis to understand head and neck cancer progression. © 2011 Macmillan Publishers Limited All rights reserved.