A new bacterial strain, displaying potent antimicrobial properties against gram-negative and gram-positive pathogenic bacteria, was isolated from food. Based on its phenotypical and biochemical properties as well as its 16S rRNA gene sequence, the bacterium was identified as Paenibacillus polymyxa and it was designated as strain OSY-DF. The antimicrobials produced by this strain were isolated from the fermentation broth and subsequently analyzed by liquid chromatography-mass spectrometry. Two antimicrobials were found: a known antibiotic, polymyxin E1, which is active against gram-negative bacteria, and an unknown 2,983-Da compound showing activity against gram-positive bacteria. The latter was purified to homogeneity, and its antimicrobial potency and proteinaceous nature were confirmed. The antimicrobial peptide, designated paenibacillin, is active against a broad range of food-borne pathogenic and spoilage bacteria, including Bacillus spp., Clostridium sporogenes, Lactobacillus spp., Lactococcus lactis, Leuconostoc mesenteroides, Listeria spp., Pediococcus cerevisiae, Staphylococcus aureus, and Streptococcus agalactiae. Furthermore, it possesses the physico-chemical properties of an ideal antimicrobial agent in terms of water solubility, thermal resistance, and stability against acid/alkali (pH 2.0 to 9.0) treatment. Edman degradation, mass spectroscopy, and nuclear magnetic resonance were used to sequence native and chemically modified paenibacillin. While details of the tentative sequence need to be elucidated in future work, the peptide was unequivocally characterized as a novel lantibiotic, with a high degree of posttranslational modifications. The coproduction of polymyxin E1 and a lantibiotic is a finding that has not been reported earlier. The new strain and associated peptide are potentially useful in food and medical applications.