The N-end rule targets specific proteins for destruction in prokaryotes and eukaryotes. Here, we report a crystal structure of a bacterial N-end rule adaptor, ClpS, bound to a peptide mimic of an N-end rule substrate. This structure, which was solved at a resolution of 1.15 A, reveals specific recognition of the peptide alpha-amino group via hydrogen bonding and shows that the peptide's N-terminal tyrosine side chain is buried in a deep hydrophobic cleft that pre-exists on the surface of ClpS. The adaptor side chains that contact the peptide's N-terminal residue are highly conserved in orthologs and in E3 ubiquitin ligases that mediate eukaryotic N-end rule recognition. We show that mutation of critical ClpS contact residues abrogates substrate delivery to and degradation by the AAA+ protease ClpAP, demonstrate that modification of the hydrophobic pocket results in altered N-end rule specificity, and discuss functional implications for the mechanism of substrate delivery.