The diversity of Paenibacillus species was assessed in the rhizospheres of four cultivars of sorghum sown in Cerrado soil amended with two levels of nitrogen fertilizer (12 and 120 kg/ha). Two cultivars (IS 5322-C and IS 6320) demanded the higher amount of nitrogen to grow, whereas the other two (FBS 8701-9 and IPA 1011) did not. Using the DNA extracted from the rhizospheres, a Paenibacillus-specific PCR system based on the RNA polymerase gene (rpoB) was chosen for the molecular analyses. The resulting PCR products were separated into community fingerprints by DGGE and the results showed a clear distinction between cultivars. In addition, clone libraries were generated from the rpoB fragments of two cultivars (IPA 1011 and IS 5322-C) using both fertilization conditions, and 318 selected clones were sequenced. Analyzed sequences were grouped into 14 Paenibacillus species. A greater diversity of Paenibacillus species was observed in cultivar IPA 1011 compared with cultivar IS 5322-C. Moreover, statistical analyses of the sequences showed that the bacterial diversity was more influenced by cultivar type than nitrogen fertilization, corroborating the DGGE results. Thus, the sorghum cultivar type was the overriding determinative factor that influenced the community structures of the Paenibacillus communities in the habitats investigated.