The use of biopreservation is a promising technique to ensure microbial safety of fresh-cut produce. The objective of this work was to test the effectiveness of the strain CPA-7 of Pseudomonas graminis against a cocktail of Salmonella spp. and Listeria monocytogenes on fresh-cut melon, and evaluate its effect on its quality during shelf-life when tested in conditions simulating commercial application. Fresh-cut melon was artificially inoculated with Salmonella spp. and L. monocytogenes and with or without the biopreservative strain at different concentrations and stored at 20, 10 and 5 °C. Moreover, the effect of the strain was tested in conditions simulating commercial application. Fresh-cut melon was packaged using passive modified atmosphere (MAP) and AIR conditions and stored at 5 and 10 °C. Quality of fresh-cut melon was evaluated in CPA-7 treated and untreated samples. At laboratory scale trials, P. graminis reduced Salmonella and L. monocytogenes growth on fresh-cut melon stored at 5, 10 and 20 °C. Effectiveness depended on their concentration and on storage temperature. At low pathogen concentration and 20 °C, L. monocytogenes growth was reduced between 2.1 and 5.3 log cfu g−1 units after 2 days of storage and Salmonella growth between 2.0 and 7.3 log cfu g−1 depending on CPA-7 dose. At 10 °C, similar reductions of pathogens were observed after 5 days of storage. In studies simulating commercial conditions, packaging atmosphere and temperature influenced P. graminis effectiveness, with better results in samples packaged under AIR conditions and 10 °C. Reduction of pathogen growth was <1-log unit in fresh-cut melon stored in MAP whilst it was >4-log units in AIR. Soluble solids content, titratable acidity, pH and firmness of fresh-cut melon were not significantly different in CPA-7 treated and untreated (control) melon. In general, lightness, chroma and hue values of fresh-cut melon stored in AIR decreased faster in CPA-7 samples than on control ones. At 5 °C, CPA-7 treated melon was visually scored lower than untreated melon. P. graminis has demonstrated promising results at 10 °C, which is a temperature more compromised for safety. Nevertheless more detailed studies on the modified atmosphere are required because AIR packaging is not recommended due to the rapid loss of quality.