Protein turnover is a critical regulatory mechanism for proteostasis. However, proteome-wide turnover quantification is technically challenging and, even in the well-studied E. coli model, reliable measurements remain scarce. Here, we quantify the degradation of ~3.2k E. coli proteins under 12 conditions by combining heavy isotope labeling with complement reporter ion quantification and find that cytoplasmic proteins are recycled when nitrogen is limited. Furthermore, we show that protein degradation rates are generally independent of cell division rates, and we used knockout experiments to assign substrates to the known ATP-dependent proteases. Surprisingly, we find that none are responsible for the observed cytoplasmic protein degradation in nitrogen limitation, suggesting that a major proteolysis pathway in E. coli remains to be discovered. Thus, we introduce broadly applicable technology for protein turnover measurements. We provide a rich resource for protein half-lives and protease substrates in E. coli, complementary to genomics data, that will allow researchers to decipher the control of proteostasis.Competing Interest StatementThe authors have declared no competing interest.