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 nonrhizosphere, but those of available Fe, Pb, and Sb had less difference between rhizosphere and nonrhizosphere. 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.