ATP-dependent protein degradation is controlled principally by substrate recognition. The AAA+ HslU ATPase is thought to bind protein substrates, denature them, and translocate the unfolded polypeptide into the HslV peptidase. The lack of well-behaved high-affinity substrates for HslUV (ClpYQ) has hampered understanding of the rules and mechanism of substrate engagement. We show that HslUV efficiently degrades Arc repressor, especially at heat-shock temperatures. Degradation depends on sequences near the N terminus of Arc. Fusion protein and peptide-binding experiments demonstrate that this sequence is a degradation tag that binds directly to HslU. Strong binding of this tag to the enzyme requires ATP and Mg(2+). Furthermore, fusion of this sequence to a protein with marked mechanical stability leads to complete degradation. Thus, these experiments demonstrate that HslUV is a powerful protein unfoldase and that initial substrate engagement by the HslU ATPase must occur after ATP binding.