Temporally and spatially controlled master regulators drive the Caulobacter cell cycle by regulating the expression of >200 genes. Rapid clearance of the master regulator, CtrA, by the ClpXP protease is a critical event that enables the initiation of chromosome replication at specific times in the cell cycle. We show here that a previously unidentified single domain-response regulator, CpdR, when in the unphosphorylated state, binds to ClpXP and, thereby, causes its localization to the cell pole. We further show that ClpXP localization is required for CtrA proteolysis. When CpdR is phosphorylated, ClpXP is delocalized, and CtrA is not degraded. Both CtrA and CpdR are phosphorylated via the same CckA histidine kinase phospho-signaling pathway, providing a reinforcing mechanism that simultaneously activates CtrA and prevents its degradation by delocalizing the CpdR/ClpXP complex. In swarmer cells, CpdR is in the phosphorylated state, thus preventing ClpXP localization and CtrA degradation. As swarmer cells differentiate into stalked cells (G1/S transition), unphosphorylated CpdR accumulates and is localized to the stalked cell pole, where it enables ClpXP localization and CtrA proteolysis, allowing the initiation of DNA replication. Dynamic protease localization mediated by a phospho-signaling pathway is a novel mechanism to integrate spatial and temporal control of bacterial cell cycle progression.