Re-vegetation is the main aim of ecological restoration projects, and in Mediterranean environments native plants are desirable to achieve successful restoration. In 1998, the burst of a tailings dam flooded the Guadiamar river valley downstream from Aznalcóllar (Southern Spain) with sludges that contained elevated concentrations of metals and metalloids, polluting soils and waters. A phytoremediation experiment to assess the potential use of native shrub species for the restoration of soils affected by the spillage was performed from 2005 to 2007, with soils divided into two groups: pH < 5 and pH > 5. Four native shrubs (Myrtus communis, Retama sphaerocarpa, Rosmarinus officinalis and Tamarix gallica) were planted and left to grow without intervention. Trace element concentrations in soils and plants, their extractability in soils, transfer factors and plant survival were used to identify the most-interesting species for phytoremediation. Total As was higher in soils with pH < 5. Ammonium sulphate-extractable zinc, copper, cadmium and aluminium concentrations were higher in very-acid soils, but arsenic was extracted more efficiently when soil pH was >5. Unlike As, which was either fixed by Fe oxides or retained as sulphide, the extractable metals showed significant relationships with the corresponding total soil metal concentration and inverse relationships with soil pH. T. gallica, R. officinalis and R. sphaerocarpa survived better in soils with pH > 5, while M. communis had better survival at pH < 5. R. sphaerocarpa showed the highest survival (30%) in all soils. Trace element transfer from soil to harvestable parts was low for all species and elements, and some species may have been able to decrease trace element availability in the soil. Our results suggest that R. sphaerocarpa is an adequate plant species for phytostabilising these soils, although more research is needed to address the self-sustainability of this remediation technique and the associated environmental changes.