Legumes are important for nitrogen cycling in the environment and agriculture due to the ability of nitrogen fixation by rhizobia. In this review, we introduce an important and potential role of legume-rhizobia symbiosis in aiding phytoremediation of some metal contaminated soils as various legumes have been found to be the dominant plant species in metal contaminated areas. Resistant rhizobia used for phytoremediation could act on metals directly by chelation, precipitation, transformation, biosorption and accumulation. Moreover, the plant growth promoting (PGP) traits of rhizobia including nitrogen fixation, phosphorus solubilization, phytohormone synthesis, siderophore release, and production of ACC deaminase and the volatile compounds of acetoin and 2, 3-butanediol may facilitate legume growth while lessening metal toxicity. The benefits of using legumes inoculated with naturally resistant rhizobia or recombinant rhizobia with enhanced resistance, as well as co-inoculation with other plant growth promoting bacteria (PGPB) are discussed. However, the legume-rhizobia symbiosis appears to be sensitive to metals, and the effect of metal toxicity on the interaction between legumes and rhizobia is not clear. Therefore, to obtain the maximum benefits from legumes assisted by rhizobia for phytoremediation of metals, it is critical to have a good understanding of interactions between PGP traits, the symbiotic plant-rhizobia relationship and metals.