The glyoxalase system, particularly glyoxalase-I (GLO-I), has been approved as a potential target for cancer treatment. In this study, a set of structurally diverse polyphenolic natural compounds were investigated as potential GLO-I inhibitors. Ellagic acid was found, computationally and experimentally, to be the most potent GLO-I inhibitor among the tested compounds which showed an IC50 of 0.71 mmol L−1. Its binding to the GLO-I active site seemed to be mainly driven by ionic interaction via its ionized hydroxyl groups with the central Zn ion and Lys156, along with other numerous hydrogen bonding and hydrophobic interactions. Due to its unique and rigid skeleton, it can be utilized to search for other novel and potent GLO-I inhibitors via computational approaches such as pharmacophore modeling and similarity search methods. Moreover, an inspection of the docked poses of the tested compounds showed that chlorogenic acid and dihydrocaffeic acid could be considered as lead compounds worthy of further optimization.