Advanced glycation end products (AGEs) are a heterogeneous group of molecules that emerge from the condensation of sugars and proteins through the Maillard reaction. Despite a significant number of studies showing strong associations between AGEs and the pathologies of aging-related illnesses, it has been a challenge to establish AGEs as causal agents primarily due to the lack of tools in reversing AGE modifications at the molecular level. Herein, we show that MnmC, an enzyme involved in a bacterial tRNA-modification pathway, is capable of reversing the AGEs carboxyethyl-lysine (CEL) and carboxymethyl-lysine (CML) back to their native lysine structure. Combining structural homology analysis, site-directed mutagenesis, and protein domain dissection studies, we generated a variant of MnmC with improved catalytic properties against CEL in its free amino acid form. We show that this enzyme variant is also active on a CEL-modified peptidomimetic and an AGE-containing peptide that has been established as an authentic ligand of the receptor for AGEs (RAGE). Our data demonstrate that MnmC variants are promising lead catalysts toward the development of AGE-reversal tools and a better understanding of AGE biology.