The consumption of fresh vegetables has been related to recurrent outbreaks of foodborne diseases (FBD) worldwide. Therefore, the development of effective alternative technologies is necessary to improve the safety of these products. This study aimed to isolate and identify epiphytic lactic acid bacteria (LAB) from fresh fruits and leafy vegetables and characterize their antagonistic capacity due to their ability to produce bacteriocins or antibacterial compounds. For this, 92 LAB isolates from fruits and leafy vegetables were screened for antagonistic activity. Two strains with the highest and broadest antagonistic activities were selected for further characterization; one from cantaloupe melon (strain CM175) and one from cilantro leaves (strain C15). The cell-free supernatants (CFS) of CM175 and C15 were found to exhibit antagonistic activity against FBD-causing pathogens. The CM175 and C15 strains were identified as Pediococcus pentosaceus and Lactobacillus graminis, respectively. Notably, the P. pentosaceus CM175 CFS stopped the growth of Salmonella Typhimurium, Salmonella Saintpaul, Staphylococcus aureus, and Listeria monocytogenes, and delayed Escherichia coli O157:H7 growth. Moreover, L. graminis C15 CFS delayed the growth of all indicator pathogens, but did not completely stop it. Organic acids and bacteriocin-like molecules were determined to be possibly exerting the observed antagonistic activity of the identified LAB strains. Thus, application of the antagonistic compounds produced by Pediococcus pentosaceus and Lactobacillus graminis could be a novel and ecological strategy in developing antimicrobial biopreservatives for the food industry and mitigating FBD by reducing the biological contamination in fruit and vegetable orchards, mainly via their potential in controlling both gram-negative and gram-positive pathogenic bacteria.