A hallmark of mammalian aging is the accumulation of irreversible molecular damage on proteins of the extracellular matrix. The advanced glycation endproduct Nε-carboxymethyl-lysine (CML) is abundant in aging human tissues, where it generates neoepitopes leading to inflammatory signaling. Here we develop CMLase, a new-to-nature enzyme engineered by testing more than 500 million enzyme variants using a novel genetic selection. We show that CMLase reverses CML modifications across diverse protein substrates, as well as human tissue from elderly donors, demonstrating for the first time that protein damage previously thought to be irreversible can be enzymatically repaired. This approach establishes a platform for developing enzymes to reverse age-related molecular damage and repair proteins compromised by aging or disease.