The evolutionarily conserved AAA+ Lon protease plays a pivotal role in protein homeostasis by precisely remodeling the proteome and specifically removing unfolded, damaged, and surplus natively folded regulatory proteins. Proteolysis by Lon comprises the three fundamental stages of substrate recognition via specific amino acid sequence motifs (degrons), ATP-fueled substrate unfolding and translocation into a sequestered proteolytic chamber, and cleavage of the translocated polypeptide by the peptidase domain. Although a plethora of Lon substrates have been identified in several bacterial species, broadly applicable rules that govern recognition of numerous substrates, and hence the ability to de novo identify new Lon substrates and regulatory pathways, has lagged behind. Similarly, cleavage-site preferences of Lon proteases, and whether these crucial enzymes from diverse bacterial species share similar preferences, has remained underexplored. In this study, we report the identification and characterization of a class of high-affinity autonomous C-terminal Yersinia Pestis (yp) Lon recognition degrons, variants of which are present in numerous known and new yp-Lon substrates and broadly distributed in diverse bacterial species. Moreover, the identification of this degron group offers the predictive power to discover new Lon substrates in eubacteria. Furthermore, cleavage-site preference analyses of multiple Lon substrates reveal that the Lon peptidase domain preferentially cleaves translocated polypeptides after Phenylalanine residues to generate peptides that range from 7 - 35 residues, with an average length of 11 residues, a general feature conserved amongst Lon proteases from phylogenetically distinct bacterial species.