A Gram-positive and endospore-forming strain, $JH8^T$, was isolated from deep-sea sediment and identified as a member of the genus Paenibacillus on the basis of 16S rRNA gene sequence and phenotypic analyses. According to a phylogenetic analysis, the most closely related species was Paenibacillus wynnii LMG $22176^T$ (96.9%). Strain $JH8^T$ was also facultatively anaerobic and grew optimally at $20-25^{circ}C$. The major cellular fatty acid was anteiso-$C_{15:0}$, and the DNA G+C content was 53.1mol%. The DNA-DNA relatedness between the isolate and Paenibacillus wynnii LMG $22176^T$ was 7.6%, indicating that strain $JH8^T$ and P. wynnii belong to different species. Based on the phylogenetic, phenotypic, and chemotaxonomic characteristics, strain $JH8^T$ would appear to belong to a novel species, for which the name Paenibacillus donghaensis sp. novo is proposed (type strain=KCTC $13049^T=LMG;237S0^T$).