A Gram-negative, nonmotile, endospore-forming, rod-shaped bacterial strain LHW35(T), which belonged to the genus Paenibacillus, was isolated from marine sediment collected from the south coast of the Republic of Korea. A phylogenetic analysis of 16S rRNA gene sequences indicated that strain LHW35(T) was most closely related to Paenibacillus taiwanensis G-soil-2-3(T) (97.2% similarity). The optimal growth conditions for strain LHW35(T) were 37°C, pH 6.0, and 0% (w/v) NaCl. The main isoprenoid quinone was menaquinone-7 (MK-7) and the major polyamine was spermidine. The diamino acid present in the cell-wall peptidoglycan was meso-diaminopimelic acid. The major fatty acids were anteiso-C15:0 and C16:0. The polar lipids were phosphatidylethanolamine, phosphatidylglycerol, unidentified amino-hospholipids, unidentified phospholipids, and unidentified polar lipids. A DNA-DNA hybridization experiment using the type strain of P. taiwanensis indicated <40% relatedness. The DNA G+C content was 45.0 mol%. Based on these phylogenetic, genomic, and phenotypic analyses, strain LHW35(T) should be classified as a novel species within the genus Paenibacillus, for which the name Paenibacillus marinisediminis sp. nov. is proposed. The type strain is LHW35(T) (=KACC 16317(T) =JCM 17886(T)).