Base excision repair (BER) is the major cellular pathway involved in removal of endogenous/spontaneous DNA lesions. Here, we study the mechanism that controls the steady-state levels of BER enzymes in human cells. By fractionating human cell extract, we purified the E3 ubiquitin ligase Mule (ARF-BP1/HectH9) as an enzyme that can ubiquitylate DNA polymerase beta (Pol beta), the major BER DNA polymerase. We identified lysines 41, 61 and 81 as the major sites of modification and show that replacement of these lysines to arginines leads to increased protein stability. We further show that the cellular levels of Pol beta and its ubiquitylated derivative are modulated by Mule and ARF and siRNA knockdown of Mule leads to accumulation of Pol beta and increased DNA repair. Our findings provide a novel mechanism regulating steady-state levels of BER proteins.