Regulated protein degradation underlies the timely execution of essential gene expression programs in bacteria. Here, we deployed time-resolved chemoproteomics, text mining of the PubMed and EcoCyc knowledge bases, and machine learning classification to discover proteolytic regulation in exponential and stationary phase Escherichia coli cultures. We experimentally validated the instability of diverse homeostatic and stress response regulators, including the principal cyclic-di-GMP phosphodiesterase PdeH, the N-end rule substrate chaperone ClpS, and all four A-type domain iron-sulfur cluster carriers, IscA, ErpA, NfuA, and SufA. Mutagenesis of the PdeH N-terminal extension abolished ClpXP recognition, which otherwise assisted in stationary phase depletion of PdeH. Unstable proteins synthesized in stationary phase such as the morphology regulator BolA, RNA polymerase ω subunit, and the biofilm regulator BssR were implicated in quiescence. Finally, machine learning–assisted substrate identification revealed Lon-mediated degradation of two opposing key regulators of surface adhesion, the RpoS antagonist FliZ and the major biofilm regulator CsgD, suggesting proteolysis may hasten transitions between motility and sessility. Together, these results highlight the role of regulated proteolysis in driving physiological adaptation for this model organism.