The strain CPA-7 of Pseudomonas graminis, isolated from apple by our group, was reported to reduce the population of foodborne pathogens in minimally processed fruit. The aim of this work was to investigate its effect on physical parameters, visual quality, enzymatic activity, vitamin C content and antioxidant activity of fresh-cut melon during refrigerated storage. CPA-7 treated or untreated fresh-cut melon was packaged under air or modified atmosphere (MAP) and stored at 5 and 10 °C for 8 days. Results showed a loss of texture during storage, above all at 10 °C. A good visual quality was observed for samples stored at 5 °C, although samples treated with the antagonistic strain CPA-7 and stored in air presented the lowest score, whereas those stored at 10 °C showed a poor visual appearance and a decrease of lightness. In general, CPA-7 treated samples presented higher POD values than untreated ones at 5 °C, and lower values at 10 °C. PPO increased during refrigerated storage regardless of the addition of the antagonist. Also, treatment with the antagonistic strain CPA-7 retained the antioxidant activity and vitamin C content of fresh-cut melon during refrigerated storage.