The cell-division cycle of Caulobacter crescentus depends on periodic activation and deactivation of the essential response regulator CtrA. Although CtrA is critical for transcription during some parts of the cell cycle, its activity must be eliminated before chromosome replication because CtrA also blocks the initiation of DNA replication. CtrA activity is down-regulated both by dephosphorylation and by proteolysis, mediated by the ubiquitous ATP-dependent protease ClpXP. Here we demonstrate that proteins needed for rapid CtrA proteolysis in vivo form a phosphorylation-dependent and cyclic diguanylate (cdG)-dependent adaptor complex that accelerates CtrA degradation in vitro by ClpXP. The adaptor complex includes CpdR, a single-domain response regulator; PopA, a cdG-binding protein; and RcdA, a protein whose activity cannot be predicted. When CpdR is unphosphorylated and when PopA is bound to cdG, they work together with RcdA in an all-or-none manner to reduce the Km of CtrA proteolysis 10-fold. We further identified a set of amino acids in the receiver domain of CtrA that modulate its adaptor-mediated degradation in vitro and in vivo. Complex formation between PopA and CtrA depends on these amino acids, which reside on alpha-helix 1 of the CtrA receiver domain, and on cdG binding by PopA. These results reveal that each accessory factor plays an essential biochemical role in the regulated proteolysis of CtrA and demonstrate, to our knowledge, the first example of a multiprotein, cdG-dependent proteolytic adaptor.