A Gram-positive, rod-shaped, xylanolytic, spore-forming bacterium, strain GTH-3(T), was isolated from a tidal flat adjacent to Ganghwa Island, Republic of Korea, and was characterized to determine its taxonomic position. On the basis of 16S rRNA gene sequence similarity, strain GTH-3(T) was shown to belong to the family Paenibacillaceae, being most closely related to the type strains of Paenibacillus ginsengisoli (94.9%), Paenibacillus anaericanus (94.8%), Paenibacillus urinalis (94.4%), Paenibacillus cookii (94.2%), Paenibacillus alvei (94.1%) and Paenibacillus chibensis (94.0%). The G+C content of the genomic DNA of strain GTH-3(T) was 45.9 +/- 0.2 mol% (mean +/- SD). The major menaquinone was MK-7. The major fatty acids were anteiso-C-15:0 and iso-C-16:0. The major polar lipids were diphosphatidylglycerol, phosphatidylglycerol and phosphatidylethanolamine. Phenotypic and chemotaxonomic data supported the affiliation of strain GTH-3(T) to the genus Paenibacillus. The results of physiological and biochemical tests allowed strain GTH-3(T) to be distinguished genotypically and phenotypically from recognized species of the genus Paenibacillus. Strain GTH-3(T) is therefore considered to represent a novel species of the genus Paenibacillus, for which the name Paenibacillus sediminis sp. nov. is proposed. The type strain is GTH-3(T) (=DSM 23491(T) =LMG 25635(T)).