Persistent infection by high-risk human papillomaviruses (HPVs) is associated with the development of cervical cancer and a subset of anogenital and head and neck squamous cell carcinomas. Abnormal expression of cellular microRNAs (miRNAs) plays an important role in the development of cancer, including HPV-related tumors. In this study, we demonstrated that miR-146a-5p was down-regulated by E6 and, less efficiently, by E7 of high-risk HPV16 in keratinocytes and the presence of low levels of this miRNA in cervical carcinoma cell lines and in high-risk HPV-positive cervical specimens. Down-regulation of miR-146a-5p was mediated at least in part by the transcription repressor c-MYC, through binding sites in the miR-146a promoter. Overexpression of miR-146a-5p significantly inhibited proliferation and migration of keratinocytes and cervical cancer cells. The histone demethylase KDM2B was validated as a new direct target of miR-146a-5p and two putative binding sites for miR-146a-5p were identified in its 3'UTR sequence. Western blot analysis and immunohistochemistry showed that KDM2B was overexpressed in HPV16 E6/E7-positive keratinocytes, in cervical cancer cell lines, and in a subset of invasive cervical carcinomas and HPV-positive laryngeal squamous cell carcinomas. In these tumors, KDM2B overexpression was associated with c-MYC copy number gain. In vitro, silencing of KDM2B inhibited proliferation of cervical cancer cells. In conclusion, this study identified a novel player, the hystone demethylase KDM2B, in HPV-mediated tumorigenesis. E6 and, less efficiently, E7 of high-risk HPV16 up-regulated KDM2B expression in human keratinocytes through a pathway involving overexpression of c-MYC, which in turn downregulated miR-146a-5p.