An investigation was conducted on the natural vegetations in the coal gangue dumps of three typical coal mine areas in Guiyang City of Guizhou Province, Southwest China, and an analysis was made on the concentrations of 10 available heavy metals in the rhizospheres of five dominant species (Pinus massoniana, Cyclobalanopsis argyrotricha, Betula luminifera, Parathelypteris chinensis, and Neyraudia reynaudiana). No significant differences were observed in the pH and EC between rhizosphere and non-rhizosphere. The concentrations of available Mn, Cd, Ni, Cr, Co, Cu, and Zn were significantly higher in rhizosphere than in nonrhizosphere, but those of available Fe, Pb, and Sb had less difference between rhizosphere and nonrhizosphere. There existed significant differences in the concentrations of available heavy metals in the rhizospheres of different dominant species. The available Mn concentration in N. reynaudiana rhizosphere was significantly higher than that in P. massoniana, C. argyrotricha, and P. chinensis rhizospheres, the available Zn concentration in B. luminifera rhizosphere was significantly higher than that in the rhizospheres of the other dominant species, and the available Cd concentration in B. luminifera rhizosphere was significantly higher than that in P. chinensis rhizosphere. B. luminifera and N. reynaudiana had most obvious rhizospheric effect, being able to be the good candidates for the phytoremediation and ecological restoration of coal gangue dumps.