Protein turnover is critical for proteostasis, but turnover quantification is challenging, and even in well-studied E. coli, proteome-wide measurements remain scarce. Here, we quantify the turnover rates of ~3200 E. coli proteins under 13 conditions by combining heavy isotope labeling with complement reporter ion quantification and find that cytoplasmic proteins are recycled when nitrogen is limited. We use knockout experiments to assign substrates to the known cytoplasmic ATP-dependent proteases. Surprisingly, none of these proteases are responsible for the observed cytoplasmic protein degradation in nitrogen limitation, suggesting that a major proteolysis pathway in E. coli remains to be discovered. Lastly, we show that protein degradation rates are generally independent of cell division rates. Thus, we present broadly applicable technology for protein turnover measurements and provide a rich resource for protein half-lives and protease substrates in E. coli, complementary to genomics data, that will allow researchers to study the control of proteostasis.