Phytoremediation is a well-known promising alternative to conventional approaches used for the remediation of diffused and moderated contaminated soils. The evaluation of the accumulation, availability, and interactions of heavy metals in soil is a priority objective for the possible use of phytoremediation techniques such as phytoextraction and phytostabilization. The soils used in this work were collected from a number of sites inside a protected area in the Apulia region (Southern Italy), which were contaminated by various heavy metals originated from the disposal of wastes of different sources of origin. Soils examined contained Cd, Cr, Cu, Ni, Pb, and Zn in amounts exceeding the critical limits imposed by EU and Italian laws. However, the alkaline conditions, high organic matter content, and silty to silty loamy texture of soils examined would suggest a reduced availability of heavy metals to plants. Due to the high total content but the low available fraction of heavy metals analyzed, especially Cr, phytoextraction appears not to be a promising remediation approach in the sites examined, whereas phytostabilization appears to be the best technique for metal decontamination in the studied areas.