A Gram-positive, rod-shaped bacterium, designated strain SCSIO N0306(T), was isolated from an abyssal sediment sample collected from the Indian Ocean. The isolate was found to grow optimally at 0-2 % (w/v) NaCl, pH 7.0 and 30 °C. Comparative analysis of the 16S rRNA gene sequence showed that the isolate SCSIO N0306(T) belongs phylogenetically to the genus Paenibacillus, and to be most closely related to P. algorifonticola XJ259(T) (with 95.47 % sequence similarity), sharing less than 95.0 % sequence similarity with all other taxa of this genus. Chemotaxonomic analysis revealed MK-7 as the major isoprenoid quinone, the DNA G+C content was determined to be 45.5 mol%, and anteiso-C15:0, C16:0, and iso-C15:0 were identified as the major fatty acids. On the basis of this polyphasic taxonomic data, isolate SCSIO N0306(T) is considered to represent a novel species of the genus Paenibacillus, for which the name Paenibacillus abyssi sp. nov. is proposed. The type strain is SCSIO N0306(T) (= DSM 26238(T) = CGMCC 1.12987(T)).