AAA+ proteases are frequently regulated by adaptors that modulate spatial and temporal control of protein turnover. Caulobacter crescentus is an alpha-proteobacterium which requires protein degradation by the AAA+ ClpXP protease for cell-cycle progression, and contains an adaptor (SspBalpha) that binds ssrA-tagged proteins and targets them to ClpXP. Here we determine the tag-binding specificity and crystal structure of SspBalpha. Despite poor sequence homology, the overall SspBalpha fold resembles orthologs from other bacteria. However, several structural features are specific to the SspBalpha subfamily, including the dimerization interface, binding surfaces optimized for ssrA-tag delivery, and residues in the tag-binding groove that act as selectivity gatekeepers for substrate recognition. Mutagenesis of these residues broadens specificity, creating a promiscuous adaptor that recognizes an expanded substrate repertoire. These results highlight general features of adaptor-mediated substrate recognition and shed light on design principles that underlie adaptor function.