Tripeptides with two consecutive prolines are the shortest and most frequent sequences causing ribosome stalling. The bacterial translation elongation factor P (EF-P) relieves this arrest, allowing protein biosynthesis to continue. A seven amino acids long loop between beta-strands β3/β4 is crucial for EF-P function and modified at its tip by lysylation of lysine or rhamnosylation of arginine. Phylogenetic analyses unveiled an invariant proline in the -2 position of the modification site in EF-Ps that utilize lysine modifications such as Escherichia coli. Bacteria with the arginine modification like Pseudomonas putida on the contrary have selected against it. Focusing on the EF-Ps from these two model organisms we demonstrate the importance of the β3/β4 loop composition for functionalization by chemically distinct modifications. Ultimately, we show that only two amino acid changes in E. coli EF-P are needed for switching the modification strategy from lysylation to rhamnosylation.