The microflora isolated from food-packaging board is dominated by paenibacilli; a number of these micro-organisms have been characterized using a polyphasic approach. The highest 16S rRNA gene similarity was found between these isolates and Paenibacillus azotofixans ATCC 35681(T) (97.7 %). The main fatty acid of the paperboard isolates was C(16 : 0) (34-45 %); straight-chain fatty acids made up 41-60 % of the total cellular fatty acids, thus distinguishing these strains from other Paenibacillus species. The paperboard isolates produced cyclodextrins from starch. The spore surface had a characteristic ribbed ornamentation. Spores and vegetative cells frequently had pilus-like appendages. Based on phylogenetic data and phenotypic and chemotaxonomic characteristics, it is proposed that the isolates represent a novel species, Paenibacillus stellifer sp. nov., with IS 1(T) (=DSM 14472(T)=CCUG 45566(T)) as the type strain.