This study used terminal restriction fragment length polymorphism (T-RFLP) analysis to determine the structure and diversity of soil bacterial populations under metal contamination and after introduction of plants for phytoremediation, and to assess the influence of soil conditions on the T-RFLP profile of these bacterial communities. Richness and diversity indices were highest in either highly contaminated soil that had undergone initial phytoremediation or in soil with low contamination, depending on the restriction enzyme used, but were consistently and significantly lowest in the highly contaminated site. The levels of As, Cd, Cu and Pb in the soil were negatively correlated to the number of ribotypes recovered and the diversity indices examined. Bacterial community re-structuring was evident in highly contaminated soil, with significant reduction in abundance or even loss of populations assigned by the phylogenetic assignment tool (PAT) mostly to Firmicutes, γ-Proteobacteria, Bacteroides and Mollicutes. In contrast, abundance of these bacteria in soils after initial phytoremediation did not significantly differ from soils of low level contamination lying farther away from the smelter. Predominance of species belonging mostly to β-proteobacteria, including populations with key roles in the nitrogen cycle (Nitrosospira, Mesorhizobium, Azoarcus) and with known function in degradation of pollutants (Burkholderia, Dechlorimonas, Desulfohalobium) were seen in highly contaminated soil. Low soil pH, low levels of N, P2O5 and exchangeable K, Ca, Al ions and as well as low CEC significantly corresponded to higher abundance of these bacteria. The capacity of these bacteria to not only survive but predominate in metal-stressed conditions suggests potential application for bioremediation and the enhancement of growth of plants for phytoremediation.