A novel strain of the genus Paenibacillus, KFC91T, was isolated from the Kafni glacier of the Himalayas. Phylogenetic analysis based on 16S rRNA gene sequences showed that strain KFC91T clustered with Paenibacillus antarcticus LMG 22078T (98.9 %) and Paenibacillus macquariensis LMG 6935T (98.7 %). The cell wall peptidoglycan contained meso-diaminopimelic acid as the diamino acid, anteiso-C15 : 0 as the predominant fatty acid and MK-7 as the major isoprenoid quinone. Based on the phylogenetic analysis, chemotaxonomic characteristics and other phenotypic traits, strain KFC91T was assigned to the genus Paenibacillus. DNA–DNA hybridization experiments of KFC91T with P. antarcticus and P. macquariensis showed reassociation values of 39 and 52 %, respectively. Thus, it is proposed that strain KFC91T should be assigned the status of a novel species of the genus Paenibacillus and the name proposed is Paenibacillus glacialis sp. nov., with KFC91T (=NCCB 100252T =DSM 22343T) as the type strain.