A Gram-stain-negative, non-motile, aerobic, endospore forming and rod-shaped bacterium, designated strain L10T, 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 L10T was associated with the genus Paenibacillus and most closely related to Paenibacillus barcinonensis BP-23T (98.2 % similarity). The major fatty acids of strain L10T were iso-C14 : 0, anteiso-C15 : 0 and iso-C16 : 0. The cell-wall peptidoglycan was the A1γ type, and the predominant isoprenoid quinone was menaquinone-7. Strain L10T 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 L10T should be classified as a novel species within the genus Paenibacillus. The name Paenibacillus oceanisediminis sp. nov. is proposed. The type strain is L10T ( = KACC 16203T = JCM 17814T).