A bacterial strain, designated PW21(T), was isolated from root nodules of Prosopis farcta in Tunisia. Phylogenetic analysis based on 16S rRNA gene sequences placed the isolate into the genus Paenibacillus, with its closest relatives being Paenibacillus glycanilyticus DS-1(T) and Paenibacillus castaneae Ch-32(T) with identity values of 96.9 %. DNA-DNA hybridization measurements showed values of less than 25 % with respect to these two species. The isolate was a Gram-variable, motile and sporulating rod. Catalase activity was positive and oxidase activity was weakly positive. Aesculin, CM-cellulose, xylan and starch were hydrolysed but casein and gelatin were not. Acetoin production was weakly positive and nitrate reduction was negative. Urease production was negative. Growth was supported by many carbohydrates and organic acids as carbon sources. MK-7 was the predominant menaquinone and anteiso-C(15 : 0), iso-C(16 : 0) and iso-C(15 : 0) were the major fatty acids. Major polar lipids were diphosphatidylglycerol, phosphatidylethanolamine, phosphatidylglycerol, a glycolipid, six phospholipids, an unidentified lipid and two unknown aminophosphoglycolipids. meso-Diaminopimelic acid was not detected in the peptidoglycan. The DNA G+C content of the isolate was 52.9 mol%. Phylogenetic, chemotaxonomic and phenotypic analyses showed that strain PW21(T) should be considered to represent a novel species of the genus Paenibacillus, for which the name Paenibacillus prosopidis sp. nov. is proposed. The type strain is PW21(T) (=LMG 25259(T) =CECT 7506(T) =DSM 22405(T)).