Two new peptide antibiotics were secreted by a Gram-positive bacterial strain isolated from fermented tomato fruit. Based on its 99% 16S rDNA sequence similarity with Paenibacillus alvei, the isolate was designated as P. alvei NP75. Among these two peptides, one is active against Gram-positive pathogens while the other against Gram-negative pathogens; thus these peptides were named as paenibacillin P and paenibacillin N, respectively. After the purification of those peptide antibiotics from the cell free culture supernatant by RP-HPLC, they were analyzed for their temperature sensitivity and susceptibility to proteases. Higher-temperature tolerant paenibacillin N was easily degraded by proteinase K, while the temperature sensitive paenibacillin P was not affected by any of the proteases used in this study other than a specific protease that was secreted by the same NP75 strain. Mass-spectrometry analysis of the above peptide antibiotics further confirmed their distinction among the known peptide antibiotics. We are reporting first of its kind the co-production of two different new peptide antibiotics from a single bacterial isolate of P. alvei strain.