In Escherichia coli, protein degradation is performed by several proteolytic machines, including ClpAP. Generally, the substrate specificity of these machines is determined by chaperone components, such as ClpA. In some cases, however, the specificity is modified by adaptor proteins, such as ClpS. Here we report the 2.5 A resolution crystal structure of ClpS in complex with the N-terminal domain of ClpA. Using mutagenesis, we demonstrate that two contact residues (Glu79 and Lys 84) are essential not only for ClpAS complex formation but also for ClpAPS-mediated substrate degradation. The corresponding residues are absent in the chaperone ClpB, providing a structural rationale for the unique specificity shown by ClpS despite the high overall similarity between ClpA and ClpB. To determine the location of ClpS within the ClpA hexamer, we modeled the N-terminal domain of ClpA onto a structurally defined, homologous AAA+ protein. From this model, we proposed a molecular mechanism to explain the ClpS-mediated switch in ClpA substrate specificity.