A Gram-stain-negative, non-motile, aerobic, endospore forming and rod-shaped bacterium, designated strain L10(T), was isolated from marine sediment collected from the South Korean coast. The organism grew optimally under conditions of 30 °C, 1 % (w/v) NaCl and pH 6.0. It was oxidase-negative and catalase-positive. Phylogenetic analysis based on 16S rRNA gene sequences indicated that strain L10(T) was associated with the genus Paenibacillus and most closely related to Paenibacillus barcinonensis BP-23(T) (98.2 % similarity). The major fatty acids of strain L10(T) were iso-C(14 : 0), anteiso-C(15 : 0) and iso-C(16 : 0). The cell-wall peptidoglycan was the A1γ type, and the predominant isoprenoid quinone was menaquinone-7. Strain L10(T) contained two unidentified lipids, an unidentified amino-phospholipid, phosphatidylethanolamine, phosphatidylglycerol, and diphosphatidylglycerol. The G+C content of the genomic DNA was 44 mol% and the DNA-DNA hybridization values with closely related strains were below 14±2 %. Based on phenotypic, genotypic, and phylogenetic data, strain L10(T) should be classified as a novel species within the genus Paenibacillus. The name Paenibacillus oceanisediminis sp. nov. is proposed. The type strain is L10(T) ( = KACC 16203(T) = JCM 17814(T)).