Most bacteria live in a dynamic environment where temperature, availability of nutrients and the presence of various chemicals vary, which requires rapid adaptation. Many of the adaptive changes are determined by changes in the transcription of global regulatory networks, but this response is slow because most bacterial proteins are stable and their concentration remains high even after transcription slows down. To respond rapidly, an additional level of regulation has evolved: the degradation of key proteins. However, as proteolysis is an irreversible process, it is subject to tight regulation of substrate binding and degradation. Here we review the roles of the proteolytic enzymes in Gram-negative bacteria and how these enzymes can be regulated to target only a subset of proteins.