A collection of bacterial endophytes isolated from stem tissues of plants growing in soils highly contaminated with petroleum hydrocarbons were screened for plant growth-promoting capabilities. Twenty-seven endophytic isolates significantly improved the growth of plants in comparison to that of uninoculated control plants. The five most beneficial isolates, one strain each of , , and and two strains of were further examined for growth promotion in , lettuce, basil, and bok choy plants. Host-specific plant growth promotion was observed when plants were inoculated with the five bacterial strains. strain M251 increased the total biomass and total root length of plants by 4.7 and 5.8 times, respectively, over that of control plants and improved lettuce and basil root growth, while strain M259 promoted shoot and root growth, lettuce and basil root growth, and bok choy shoot growth. A genome comparison between strains M251 and M259 showed that both genomes contain up to 70 actinobacterial putative plant-associated genes and genes involved in known plant-beneficial pathways, such as those for auxin and cytokinin biosynthesis and 1-aminocyclopropane-1-carboxylate deaminase production. This study provides evidence of direct plant growth promotion by The discovery of new plant growth-promoting bacteria is necessary for the continued development of biofertilizers, which are environmentally friendly and cost-efficient alternatives to conventional chemical fertilizers. Biofertilizer effects on plant growth can be inconsistent due to the complexity of plant-microbe interactions, as the same bacteria can be beneficial to the growth of some plant species and neutral or detrimental to others. We examined a set of bacterial endophytes isolated from plants growing in a unique petroleum-contaminated environment to discover plant growth-promoting bacteria. We show that strains of exhibit strain-specific plant growth-promoting effects on four different plant species.