A bacterial strain, designated PALXIL04(T), was isolated from the phyllosphere of Phoenix dactylifera. Phylogenetic analysis placed the isolate within the genus Paenibacillus with the closest relatives being Paenibacillus curdlanolyticus and Paenibacillus kobensis. DNA-DNA hybridization measurements showed low DNA relatedness (15-20 %) between the isolate and its closest relatives. Cells were Gram-variable, facultatively anaerobic, motile, sporulating rods. Catalase and oxidase were produced by the organism. Cellulose, starch, aesculin and xylan were hydrolysed. Growth was supported by many carbohydrates as the carbon source. MK-7 was the predominant menaquinone and anteiso-C(15 : 0) the major fatty acid. The G+C content of the DNA was 50.7 mol%. Phylogenetic, DNA-DNA relatedness and phenotypic analyses indicated that strain PALXIL04(T) represents a novel species of the genus Paenibacillus, for which the name Paenibacillus phyllosphaerae sp. nov. is proposed. The type strain is PALXIL04(T) (=LMG 22192(T)=CECT 5862(T)).