Legumes are ideal for revegetation of metal-mined wastelands which lack nitrogen (N). A greenhouse study was conducted to investigate the feasibility of using Sesbania rostrata and S. cannabina for the reclamation of lead/zinc (Pb/Zn) mine tailings and to evaluate the effects of organic amendment using sewage sludge (0%, 25%, 50%, and 75%, v/v). The results showed that both species could continue to grow on the highly toxic tailings substrata for at least 80 days, although their growth suffered from adverse effects. That S. rostrata with stem and root nodules had better growth (biomass, growth rates, and biomass of nodules) than S. cannabina suggested that S. rostrata is a better choice as a pioneer species for revegetation of the mine tailings. Stem nodules had less obvious adverse effects imposed by tailings than root nodules. Application of sewage sludge increased contents of total carbon (C), N, phosphorus (P), and potassium (K), and reduced total Zn, Pb, Cd, and DTPA-extractable Pb and Cd in tailings substrata. These, in turn, reduced metal (Zn, Pb, and Cd) uptake and accumulation in plant tissues, and improved plant growth performance, including biomass, growth rates, stem nodulation. Fifty percent (v/v) of sludge application rate was the best loading rate for plant growth.