Heavy metal- and organic-contaminated sites are ubiquitous, but few studies have been conducted to address such an issue. EDTA- and SDS-enhanced washing was studied for remediation of Pb- and/or marine diesel fuel (MDF)-contaminated soils. The feasibility of recovery and reuse of EDTA and SDS, as well as the physicochemical interactions among the chemical agents, contaminants and soils were extensively investigated using batch experiments. The optimal washing sequence was then determined. The experimental results showed that EDTA could be recovered and reused for four cycles without significant loss of its chelating capacity, while the extraction capability of SDS was noticeably reduced after each reuse cycle. The free phase of marine diesel fuel (MDF) in soils physically isolated the sorbed Pb on soils and thus reducing its extraction by EDTA. The presence of SDS alone or together with low concentration of EDTA was found to enhance Pb removal probably via electrostatic interaction and dissolution of soil organic matter. However, it hindered Pb extraction by high concentration of EDTA, because of the potential formation of complexes between some strongly-bound Pb and SDS, that are more resistant to desorption. Therefore, EDTA washing followed by SDS achieved the highest Pb removal efficiency. On the other hand, MDF removal by SDS was significantly hindered by coexisting Pb in soils, probably because the formation of Pb-dodecyl sulfate (DS) complex would decrease the effective amount of SDS available for forming micelles in solution and enhance MDF sorption. EDTA alone or together with SDS could enhance MDF removal, but the residual MDF after EDTA-washing became more resistant to SDS removal. Consequently, SDS washing followed by EDTA is considered as the optimal washing sequence for MDF removal.