Intensive mining and processing activities worldwide resulted in the generation of huge amounts of waste (tailings), generally characterized as toxic, radioactive, and/or hazardous. The exposure potential and, hence, the risk posed by such wastes is enhanced by a general lack of vegetation. Phytostabilization has proven to be efficient in reducing this risk. However, establishing vegetation on tailing dumps may be expensive due to the intensive use of amendments and chemical fertilizers. In this article, investigations on artificial inoculation of mine tailings with bacterial strains as a means to improve the development of vegetative covers and reduce application cost by eliminating chemical fertilization are presented and discussed. The development of plants and microbial communities from tailings, as well as the impact of inoculation on metal uptake in plants, were studied. Experiments were carried out in greenhouse using two types of mine tailings (phosphogypsum and sulphidic tailings) from the Romanian Black Sea coast. Indigenous herbaceous plants were cultivated on tailings with the addition of chemical fertilizers versus bacterial inoculation. After a 6-month experimental period, excellent plant growth, which is associated with a rich microbial community, was observed in all inoculated treatments, in contrast with poor plant growth and microbiota from the chemical fertilization treatments alone. Additionally, artificial inoculation improved plant resistance to heavy metals by reducing the uptake of some toxic metals. Once a rich microbial community is established, inoculation may be discontinued. Based on these results, efficient and cost-effective phytostabilization schemes can be proposed.