Our aim was to assess the efficacy of four different bioremediation strategies applied to soil treated with urban sediments for alleviating soil phytotoxicity (examined using Lepidium sativum), by removing polychlorinated dibenzo-p-dioxins (PCDDs) and polychlorinated dibenzofurans (PCDFs), and mitigating the toxic effect on plants by the applied sediment: (1) Natural attenuation, (2) phytoremediation with the use of two plants Tagetes patula L. and Festuca arundinacea, (3) rhizobacterial inoculation with Massilia niastensis p87 and Streptomyces costaricanus RP92 strains, (4) rhizobacteria-assisted phytoremediation with both plants and strains. The applied sediment had a positive influence on L. sativum growth (90% higher than in the unamended soil), mostly due to its high content of nutrients, mainly Ca and Fe, which immobilize pollutants. The positive effect of sediments continued for up to 10-week duration of the experiment; however, the rhizobacterial inoculated samples were characterized by higher growth of L. sativum. The application of rhizobacteria-assisted phytoremediation further increased the growth of L. sativum, and was also found to improve the efficiency of PCDD/PCDF removal, resulting in a maximum 44% reduction of its content. This strategy also alleviated the negative impact of urban sediments on T. patula and F. arundinacea biomass, and had a beneficial effect on protein and chlorophyll content in the studied plants.