Aiming to reduce food spoilage, the present study developed novel highly active food-grade preservatives affecting a wide range of bacteria. For this purpose, storage proteins were extracted from food plants. After enzymatic hydrolysis by the digestive protease chymotrypsin, the peptide profiles were analyzed by ultrahigh-performance micro-liquid chromatography–triple quadrupole time-of-flight tandem mass spectrometry. Virtual screening identified 21 potential antimicrobial peptides in chickpea legumin. Among those, the peptides Leg1 (RIKTVTSFDLPALRFLKL) and Leg2 (RIKTVTSFDLPALRWLKL) exhibited antimicrobial activity against 16 different bacteria, including pathogens, spoilage-causing bacteria and two antibiotic-resistant strains. Minimum inhibitory concentrations (MIC) down to 15.6 µM indicated 10–1,000-fold higher activity of the novel antimicrobial peptides compared to conventional food preservatives. Moreover, Leg1 and Leg2 showed bactericidal activity in bacterial suspension and during the storage of raw pork meat.