The N-end rule states that the half-life of a protein is determined by the nature of its amino-terminal residue. Eukaryotes and prokaryotes use N-terminal destabilizing residues as a signal to target proteins for degradation by the N-end rule pathway. In eukaryotes an E3 ligase, N-recognin, recognizes N-end rule substrates and mediates their ubiquitination and degradation by the proteasome. In Escherichia coli, N-end rule substrates are degraded by the AAA + chaperone ClpA in complex with the ClpP peptidase (ClpAP). Little is known of the molecular mechanism by which N-end rule substrates are initially selected for proteolysis. Here we report that the ClpAP-specific adaptor, ClpS, is essential for degradation of N-end rule substrates by ClpAP in bacteria. ClpS binds directly to N-terminal destabilizing residues through its substrate-binding site distal to the ClpS-ClpA interface, and targets these substrates to ClpAP for degradation. Degradation by the N-end rule pathway is more complex than anticipated and several other features are involved, including a net positive charge near the N terminus and an unstructured region between the N-terminal signal and the folded protein substrate. Through interaction with this signal, ClpS converts the ClpAP machine into a protease with exquisitely defined specificity, ideally suited to regulatory proteolysis.