The present study pays special attention to lactic acid bacteria products, cyclic dipeptides (CDPs), as an effective prevention strategy that can be used to eradicate the threats posed by multidrug-resistant (MDR) Enterobacteriaceae. Herein, Lactiplantibacillus plantarum MC39, a strain isolated from an artisanal Egyptian cheese, was a producer of a novel CDP that could strongly inhibit, in vitro, MDR Klebsiella pneumoniae W8 and Enterobacter hormaechei U25, for the first time. Following partial purification with 80% ammonium sulphate precipitation and Sephadex G-100 chromatography, this biomolecule was identified as the cyclic dipeptide cyclo(Ala–Glu) using IR, HNMR, and LC–MS. Cyclo(Ala–Glu) was thermostable up to 121 °C, insensitive to pepsin and α-chymotrypsin, tolerant to organic solvents, active at acidic pH, and stable for 45 days of storage. Thus, it shows clear evidence to be usable as a bio-preservative in dairy products and as a potential therapeutic agent, controlling MDR K. pneumoniae and E. hormaechei.