A novel bacterial strain Sl 79T was isolated from a deep surface sediment sample obtained from the Sea of Japan and investigated by phenotypic and molecular methods. The bacterium Sl 79T was Gram-positive, facultatively anaerobic, spore-forming, motile and able to form two different types of colonies. It contained the major menaquinone MK-7 and anteiso-C15:0 followed by iso-C15:0 as predominant fatty acids. Phylogenetic analysis based on 16S rRNA gene sequences revealed that strain Sl 79T belonged to the genus Paenibacillus where it clustered to Paenibacillus apiarius NRRL NRS-1438T with a sequence similarity of 97.7 % and sharing sequence similarities below than 96.7 % to other validly named Paenibacillus species. Strain Sl 79T was found to possess a remarkable inhibitory activity against indicatory microorganisms. On the basis of combined spectral analyses, strain Paenibacillus sp. Sl 79T was established to produce isocoumarin and novel peptide antibiotics. On the basis of DNA–DNA relatedness, phenotypic and phylogenetic data obtained, it was concluded that strain Sl 79T represents a novel species, Paenibacillus profundus sp. nov. with the type strain Sl 79T = KMM 9420T = NRIC 0885T.