This paper tests a soil washing process using flotation in its effectiveness for the removal of both polycyclic aromatic hydrocarbons (PAHs) and Pb from three polluted soils (soils A, B and C). The optimal flotation conditions were defined as: pulp density=10%, Cocamidopropylhydroxysultaine (CAS)=0.2% ww(-1), [NaCl]=5.5M, pH=3, flotation time=15 min, air flow rate=3l min(-1), stirring speed=1800 rpm and temperature=20 degrees C. Under these conditions, successive flotation stages (n), decreased the contaminant content to below permitted levels (up to 90% PAHs and Pb removal). Thus, a more contaminated matrix required the addition of a growing number of successive flotation stages to lower contamination levels below legal thresholds. While PAHs were distributed within the solid fractions of the process, Pb was mainly present in the liquid fractions. Electrodeposition allowed a total recovery of Pb after 60 min using a 2A electrical current.