Sixteen gram-positive endospore-forming bacteria previously isolated from soil, plant rhizospheres, plant roots and pasteurized pureed vegetables were studied to determine their taxonomic positions. The isolates were formerly identified as Bacillus circulans based on their biochemical characters using API galleries. Two of these strains, RSA19T and TOD45T, were recently assigned to the genus Paenibacillus based on phylogenetic analysis of their 16S rRNA (rrs) gene sequence. In the present work, the sixteen isolates were assigned to two genomospecies using DNA-DNA hybridization, in agreement with rrs gene sequence analysis. These genomospecies can also be differentiated on the basis of their cultural and biochemical characters into two novel species, for which the names Paenibacillus graminis sp. nov. (type strain RSA19T = ATCC BAA-95T = LMG 19080T) and Paenibacillus odorifer sp. nov. (type strain TOD45T = ATCC BAA-93T = LMG 19079T) are proposed.