Ribonucleotide reductase M1 (RRM1) is required for mammalian deoxyribonucleotide (dNTP) metabolism. It is the primary target of the antimetabolite drug gemcitabine, which is among the most efficacious and most widely used cancer therapeutics. Gemcitabine directly binds to RRM1 and irreversibly inactivates ribonucleotide reductase. Intra-tumoral RRM1 levels are predictive of gemcitabine's therapeutic efficacy. The mechanisms that regulate intracellular RRM1 levels are largely unknown. Here, we identified the E3 ubiquitin-protein ligases RNF2 and Bmi1 to associate with RRM1 with subsequent poly-ubiquitination at either position 48 or 63 of ubiquitin. The lysine residues 224 and 548 of RRM1 were identified as major ubiquitination sites. We show that ubiquitinated RRM1 undergoes proteasome-mediated degradation and that targeted post-transcriptional silencing of RNF2 and Bmi1 results in increased RRM1 levels and resistance to gemcitabine. Immunohistochemical analyses of 187 early-stage lung cancer tumor specimens revealed a statistically significant co-expression of RRM1 and Bmi1. We were unable to identify suitable reagents for in situ quantification of RNF2. Our findings suggest that Bmi1 and possibly RNF2 may be attractive biomarkers of gemcitabine resistance in the context of RRM1 expression. They also provide novel information for the rational design of gemcitabine-proteasome inhibitor combination therapies, which so far have been unsuccessful if given to patients without taking the molecular context into account.