A Gram-stain-positive, motile, endospore-forming, and strictly aerobic rod-shaped bacterium designated DS80T was isolated from an island soil. The strain DS80T grew at temperatures between 15 and 40°C (optimum = 30°C) and at pH values ranging from 5.0 to 9.0 (optimum = 7.0). The phylogenetic analysis based on the comparisons of the 16S rRNA gene sequences showed that the isolate was affiliated to the genus Paenibacillus and was mostly related to Paenibacillus assamensis GPTSA11T (with the sequence similarity of 96.33%) and Paenibacillus urinalis 5402403T(95.48%). The G+C content of the genomic DNA was 44.0 mol% and the major fatty acids were anteiso-C15:0, iso-C15:0, iso-C16:0, and C16:1 ω11c. Strain DS80T contained MK-7 as the major menaquinone, and phosphatidylglycerol, phosphatidylethanolamine, and diphosphatidylglycerol as the major polar lipids. The peptidoglycan contained a major amount of meso-diaminopimelic acid. The chemotaxonomic profile of strain DS80T was consistent with that of Paenibacillus. However, the phenotypic properties clearly separated the strain from other species of the genus. Accordingly, a new species, Paenibacillus insulae sp. nov., is proposed (type strain =DS80T =JCM 17278T =KCTC 13833T).