Regulated protein degradation is essential. The timed destruction of crucial proteins by the ClpXP protease drives cell-cycle progression in the bacterium Caulobacter crescentus. Although ClpXP is active alone, additional factors are inexplicably required for cell-cycle-dependent proteolysis. Here, we show that these factors constitute an adaptor hierarchy wherein different substrates are destroyed based on the degree of adaptor assembly. The hierarchy builds upon priming of ClpXP by the adaptor CpdR, which promotes degradation of one class of substrates and also recruits the adaptor RcdA to degrade a second class of substrates. Adding the PopA adaptor promotes destruction of a third class of substrates and inhibits degradation of the second class. We dissect RcdA to generate bespoke adaptors, identifying critical substrate elements needed for RcdA recognition and uncovering additional cell-cycle-dependent ClpXP substrates. Our work reveals how hierarchical adaptors and primed proteases orchestrate regulated proteolysis during bacterial cell-cycle progression.