Heavy metals can cause serious contamination of soils, especially in mining regions. A detailed understanding of the effects of heavy metals on plants and root-associated microbial communities could help to improve phytoremediation systems. In this study, black locust (Robinia pseudoacacia) seedlings with or without rhizobial inoculation were planted in soils contaminated with different levels of heavy metals. Bacterial communities in rhizosphere and bulk soil samples were analyzed using 16S rRNA gene sequencing on the Illumina MiSeq platform and shotgun metagenome sequencing on the Illumina HiSeq platform. Soil bacterial communities varied significantly depending on the level of soil contamination, and planting also had some influence. Although inoculation of Mesorhizobium loti HZ76 (a natural microsymbiont of R. pseudoacacia) was a relatively minor factor, it did influence the soil bacterial community. Under the selective pressure, plant growth promotion-related biomarkers in the rhizosphere increased after inoculation compared with non-inoculated controls, especially those associated with Mesorhizobium, Variovorax, Streptomyces, and Rhodococcus genera. Genes encoding ATP-binding cassette transporters were up-regulated in the rhizosphere after inoculation compared with genes related to sulfur/nitrogen metabolism. These results provide insight into soil bacterial communities and their functions in the R. pseudoacacia rhizosphere in response to rhizobial inoculation and heavy metal contamination. This knowledge may prove useful for improving phytoremediation of metal-contaminated soils.