Bmi-1, the first functionally identified polycomb gene family member, plays critical roles in cell cycle regulation, cell immortalization, and cell senescence. Bmi-1 is involved in the development and progression of carcinomas and is a potent target for cancer therapy. One important pathway regulated by Bmi-1 is that involving two cyclin-dependent kinase inhibitors, p16(Ink4a) and p19(Arf), as Bmi-1 represses the INK4a locus on which they are encoded. A close correlation between the up-regulation of Bmi-1 and down-regulation of p16 has been demonstrated in various tumors; however, how Bmi-1 regulates p16 expression is not clear. In this study, we revealed that Bmi-1 regulates the expression of p16 by binding directly to the Bmi-1-responding element (BRE) within the p16 promoter. The BRE resided at bp -821 to -732 upstream of the p16 ATG codon. BRE alone was sufficient to allow Bmi-1-mediated regulation of the CMV promoter. Bmi-1 typically functions by forming a complex with Ring2; however, regulation of p16 was independent of Ring2. Chromatin immunoprecipitation sequencing of Bmi-1-precipitated chromatin DNA revealed that 1536 genes were targeted by Bmi-1, including genes involved in tissue-specific differentiation, cell cycle, and apoptosis. By analyzing the binding sequences of these genes, we found two highly conserved Bmi-1-binding motifs, which were required for Bmi-1-mediated p16 promoter regulation. Taken together, our results revealed the molecular mechanism of Bmi-1-mediated regulation of the p16 gene, thus providing further insights into the functions of Bmi-1 as well as a sensitive high-throughput platform with which to screen Bmi-1-targeted small molecules for cancer therapy.