Degradation of intracellular proteins in Gram-negative bacteria regulates various cellular processes and serves as a quality control mechanism by eliminating damaged proteins. To understand what causes the proteolytic machinery of the cell to degrade some proteins while sparing others, we employed a quantitative pulsed-SILAC (Stable Isotope Labeling with Amino acids in Cell culture) method followed by mass spectrometry analysis to determine the half-lives for the proteome of exponentially growing Escherichia coli, under standard conditions. We developed a likelihood-based statistical test to findactively degraded proteins, and identified dozens of novel proteins that are fast-degrading. Finally, we used structural, physicochemical and protein-protein interaction network descriptorsto train a machine-learning classifier to discriminate fast-degrading proteins from the rest of the proteome. Our combined computational-experimental approach provides means for proteomic-based discovery of fast degrading proteins in bacteria and the elucidation of the factors determining protein half-livesand have implications for protein engineering. Moreover, as rapidly degraded proteins may play an important role in pathogenesis, our findings could identify new potential antibacterial drug targets