Forty-two strains representing the eight recognized nitrogen-fixing Paenibacillus species and 12 non-identified strains were examined by restriction fragment length polymorphism (RFLP) analysis of part of 16S and 23S rRNA genes amplified by polymerase chain reaction (PCR). Eleven different 16S rDNA genotypes were obtained from the combined data of RFLP analysis with four endonucleases and they were in agreement with the established taxonomic classification. Only one group of unclassified strains (Group I) was assigned in a separate genotype, suggesting they belong to a new species. Using the 23S PCR-RFLP method only six genotypes were detected, showing that this method is less discriminative than the 16S PCR-RFLP. Using the multilocus enzyme electrophoresis (MLEE) assay, the 48 strains tested could be classified into 35 zymovars. The seven enzymatic loci tested were polymorphic and the different profiles obtained among strains allowed the grouping of strains into 10 clusters. The PCR-RFLP methods together with the MLEE assay provide a rapid tool for the characterization and the establishment of the taxonomic position of isolates belonging to this nitrogen-fixing group, which shows a great potentiality in promoting plant growth.