ClpXP, an ATP-dependent protease, degrades hundreds of different intracellular proteins. ClpX chooses substrates by binding peptide tags, typically displayed at the N or C terminus of the protein to be degraded. Here, we identify a ClpX mutant that displays a 300-fold change in substrate specificity, resulting in decreased degradation of ssrA-tagged substrates but improved degradation of proteins with other classes of degradation signals. The altered-specificity mutation occurs within "RKH" loops, which surround the entrance to the central pore of the ClpX hexamer and are highly conserved in the ClpX subfamily of AAA+ ATPases. These results support a major role for the RKH loops in substrate recognition and suggest that ClpX specificity represents an evolutionary compromise that has optimized degradation of multiple types of substrates rather than any single class.