Bacteria are frequently exposed to changes in environmental conditions, such as fluctuations in temperature, pH or the availability of nutrients. These assaults can be detrimental to cell as they often result in a proteotoxic stress, which can cause the accumulation of unfolded proteins. In order to restore a productive folding environment in the cell, bacteria have evolved a network of proteins, known as the protein quality control (PQC) network, which is composed of both chaperones and AAA+ proteases. These AAA+ proteases form a major part of this PQC network, as they are responsible for the removal of unwanted and damaged proteins. They also play an important role in the turnover of specific regulatory or tagged proteins. In this review, we describe the general features of an AAA+ protease, and using two of the best-characterised AAA+ proteases in Escherichia coli (ClpAP and ClpXP) as a model for all AAA+ proteases, we provide a detailed mechanistic description of how these machines work. Specifically, the review examines the physiological role of these machines, as well as the substrates and the adaptor proteins that modulate their substrate specificity.