A bacterial strain designated PALXIL08(T) was isolated from the phyllosphere of Phoenix dactylifera bracts. A phylogenetic analysis based on the 16S rRNA gene sequence placed the isolate within the genus Paenibacillus in the same subgroup as Paenibacillus kobensis and Paenibacillus curdlanolyticus (98.9 and 97.9 % sequence similarity, respectively). The DNA hybridization values between the isolate and the type strains of Paenibacillus kobensis and Paenibacillus curdlanolyticus were found to be 27.4 and 17.6 %, respectively. The isolate comprised Gram-variable, facultatively anaerobic, motile, sporulating rods. Catalase and oxidase were produced and cellulose, xylan, starch and aesculin were hydrolysed. Many carbohydrates served as carbon sources for growth. MK-7 was the predominant menaquinone, and anteiso-C(15 : 0) and iso-C(16 : 0) were the major fatty acids. The DNA G+C content was 51 mol%. DNA relatedness data and the results of phylogenetic and phenotypic analyses showed that strain PALXIL08(T) should be considered as the type strain of a novel species of the genus Paenibacillus, for which the name Paenibacillus cellulosilyticus sp. nov. is proposed. The type strain is PALXIL08(T) (=LMG 22232(T)=CECT 5696(T)).