Bacillus mucilaginosus and Bacillus edaphicus were reclassified based on their 16S rRNA and gyrB gene sequences, DNA-DNA hybridization, fatty acid methyl esters and other taxonomic characteristics. Phylogenetic analysis based on 16S rRNA and gyrB gene sequences indicated that strains of B. mucilaginosus and B. edaphicus were members of the genus Paenibacillus, with over 90.4 % and 70.3 % sequence similarity, respectively. Their DNA G+C contents were 54.5-56.8 mol%. The DNA-DNA relatedness values of B. edaphicus VKPM B-7517(T) with B. mucilaginosus KNP414 and B. mucilaginosus CGMCC 1.236 were 89.2 % and 88.7 %, respectively. The major isoprenoid quinone of B. mucilaginosus and B. edaphicus was MK-7 (94.1-95.7 %). The peptidoglycan type was A1gamma (meso-diaminopimelic acid) and the major polar lipids were phosphatidylglycerol and diphosphatidylglycerol. The major fatty acids were anteiso-C(15 : 0), C(16 : 1)omega11c and C(16 : 0). Phenotypic features and fatty acid profiles supported the similarity of B. mucilaginosus and B. edaphicus to Paenibacillus validus CCTCC 95016(T) and confirmed their relationship with members of the genus Paenibacillus. Therefore, it is proposed that Bacillus mucilaginosus and Bacillus edaphicus be transferred to the genus Paenibacillus as Paenibacillus mucilaginosus comb. nov. (type strain HSCC 1605(T)=VKPM B-7519(T)=VKM B-1480D(T)=CIP 105815(T)=KCTC 3870(T)) and Paenibacillus edaphicus comb. nov. (type strain VKPM B-7517(T)=DSM 12974(T)=CIP 105814(T)), respectively.