Elongation factor P (EF-P) is a conserved ribosome-binding protein that structurally mimics tRNA to enable the synthesis of peptides containing motifs that otherwise would induce translational stalling, including polyproline. In many bacteria, EF-P function requires post-translational modification with (R)-β-lysine by the lysyl-tRNA synthetase paralog PoxA. To investigate how recognition of EF-P by PoxA evolved from tRNA recognition by aminoacyl-tRNA synthetases, we compared the roles of EF-P/PoxA polar contacts with analogous interactions in a closely related tRNA/synthetase complex. PoxA was found to recognize EF-P solely via identity elements in the acceptor loop, the domain of the protein that interacts with the ribosome peptidyl transferase center and mimics the 3'-acceptor stem of tRNA. Although the EF-P acceptor loop residues required for PoxA recognition are highly conserved, their conservation was found to be independent of the phylogenetic distribution of PoxA. This suggests EF-P first evolved tRNA mimicry to optimize interactions with the ribosome, with PoxA-catalyzed aminoacylation evolving later as a secondary mechanism to further improve ribosome binding and translation control.