Soil pollution by trace elements (TEs) from mining and industrial activity is widespread and presents a risk to humans and ecosystems. The use of trees to immobilize TEs (phytostabilization) is a low-cost and effective method of soil remediation. We aimed to determine the chemical composition of leaves and flower buds of Eucalyptus camaldulensis in seven sites along the Guadiamar River valley (SW Spain), an area contaminated by a mine-spill in 1998. E. camaldulensis trees in the spill-affected area and adjacent non affected areas were growing on a variety of soils with pH from 5.6 to 8.1 with low concentration of plant nutrients. The spill affected soils contained up to 1069 mg kg-1 of As and 4086 mg kg-1 of Pb. E. camaldulensis tolerated elevated TE concentrations in soil and, compared to other species growing in the same environment, had low TE concentrations in the aerial portions. Besides tolerance to soil contamination, E. camaldulensis had low bioaccumulation coefficients for soil contaminants. TE concentrations in the aboveground portions were below levels reported to be toxic to plants or ecosystems. Flower buds had even lower TE concentrations than leaves. Despite the relatively low concentration of TEs in leaves they were significantly correlated with the soil extractable (0.01 M CaCl2) Cd, Mn and Zn (but not Cu and Pb). The general features of this tree species: tolerance to impoverished and contaminated soils, fast growth and deep root system, and low transfer of TEs from soil to aboveground organs makes it suitable for phytostabilization of soils contaminated by TEs. In addition, eucalyptus leaves could be used for biomonitoring the soil extractability of Cd, Mn and Zn but not Cu or Pb.