A bacterial strain designated PM10T was isolated from root nodules of Periandra mediterranea in Brazil. Phylogenetic analyses based on 16S rRNA gene sequences placed the isolate in the genus Paenibacillus with its closest relatives being Paenibacillus vulneris CCUG 53270T and Paenibacillus yunnanensis YN2T with 95.6 and 95.9% 16S rRNA gene sequence similarity, respectively. The isolate was a Gram-stain-variable, motile, sporulating rod that was catalase-negative and oxidase-positive. Caseinase was positive, amylase was weakly positive and gelatinase was negative. Growth was supported by many carbohydrates and organic acids as carbon sources. MK-7 was the only menaquinone detected and anteiso-C15 : 0 was the major fatty acid. Major polar lipids were diphosphatidylglycerol, phosphatidylmonomethylethanolamine, phosphatidylethanolamine, phosphatidylglycerol and two unidentified lipids. meso-Diaminopimelic acid was detected in the peptidoglycan. The DNA G+C content was 52.9 mol%. Phylogenetic, chemotaxonomic and phenotypic analyses showed that strain PM10T should be considered representative of a novel species of the genus Paenibacillus, for which the name Paenibacillus periandrae sp. nov. is proposed. The type strain is PM10T (=LMG 28691T=CECT 8827T).