Unknown mechanisms govern degradation of the p19Arf tumor suppressor, an activator of p53 and inhibitor of ribosomal RNA processing. Kinetic metabolic labeling of cells with [3H]-leucine indicated that p19Arf is a relatively stable protein (half-life ∼6 h) whose degradation depends upon the ubiquitin–proteasome pathway. Although p19Arf binds to the Mdm2 E3 ubiquitin protein ligase to activate p53, neither of these molecules regulates p19Arf turnover. In contrast, the nucleolar protein nucleophosmin/B23, which binds to p19Arf with high stoichiometry, retards its turnover, and Arf mutants that do not efficiently associate with nucleophosmin/B23 are unstable and functionally impaired. Mouse p19Arf, although highly basic (22% arginine content), contains only a single lysine residue absent from human p14ARF, and substitution of arginine for lysine in mouse p19Arf had no effect on its rate of degradation. Mouse p19Arf (either wild-type or lacking lysine) and human p14ARF undergo N-terminal polyubiquitination, a process that has not as yet been documented in naturally occurring lysine-less proteins. Re-engineering of the p19Arf N terminus to provide consensus sequences for N-acetylation limited Arf ubiquitination and decelerated its turnover.