Different species of Paenibacillus are considered to be plant growth-promoting rhizobacteria (PGPR) due to their ability to repress soil borne pathogens, fix atmospheric nitrogen, induce plant resistance to diseases and/or produce plant growth-regulating substances such as auxins. Although it is known that indole-3-acetic acid (IAA) is the primary naturally occurring auxin excreted by Paenibacillus species, its transport mechanisms (auxin efflux carriers) have not yet been characterized. In this study, the auxin production of P. polymyxa and P. graminis, which are prevalent in the rhizospheres of maize and sorghum sown in Brazil, was evaluated. In addition, the gene encoding the Auxin Efflux Carrier (AEC) protein from P. polymyxa DSM36T was sequenced and used to determine if various strains of P. polymyxa and P. graminis possessed this gene. Each of the 68 P. polymyxa strains evaluated in this study was able to produce IAA, which was produced at concentrations varying from 1 to 17 μg/ml. However, auxin production was not detected in any of the 13 P. graminis strains tested in this study. Different primers were designed for the PCR amplification of the gene coding for the AEC in P. polymyxa, and the predicted protein of 319 aa was homologous to AEC from Bacillus amyloliquefaciens, B. licheniformis, and B. subtilis. However, no product was observed when these primers were used to amplify the genomic DNA of seven strains of P. graminis, which suggests that this gene is not present in this species. Moreover, none of the P. graminis genomes tested were homologous to the gene coding for AEC, whereas all of the P. polymyxa genomes evaluated were. This is the first study to demonstrate that the AEC protein is present in P. polymyxa genome.