In the bacterial cytosol, ATP-dependent protein degradation is performed by several different chaperone-protease pairs, including ClpAP. The mechanism by which these machines specifically recognize substrates remains unclear. Here, we report the identification of a ClpA cofactor from Escherichia coli, ClpS, which directly influences the ClpAP machine by binding to the N-terminal domain of the chaperone ClpA. The degradation of ClpAP substrates, both SsrA-tagged proteins and ClpA itself, is specifically inhibited by ClpS. In contrast, ClpS enhanced ClpA recognition of two heat-aggregated proteins in vitro and, consequently, the ClpAP-mediated disaggregation and degradation of these substrates. We conclude that ClpS modifies ClpA substrate specificity, potentially redirecting degradation by ClpAP toward aggregated proteins.