The present manuscript presents a convenient method for the synthesis of iron/carbon (Fe/C) nanoparticles (NPs) coated with much smaller Pd NPs for the removal of halogenated organic pollutants. For this purpose, iron oxide/polyvinylpyrrolidone (IO/PVP) NPs were first prepared by the thermal decomposition of ferrocene mixed with PVP at 350 °C under an inert atmosphere. IO,Fe/C and Fe/C NPs coated with graphitic and amorphous carbon layers were then produced by annealing the IO/PVP NPs at 500 and 600 °C, respectively, under an inert atmosphere. The effect of the annealing temperature on the chemical composition, shape, crystallinity, surface area and magnetic properties of the IO/PVP, IO,Fe/C and Fe/C NPs has been elucidated. Air-stable Fe/C/Pd NPs were produced by mixing the precursor palladium acetate with the air-stable Fe/C NPs in ethanol. The obtained Fe/C/Pd NPs demonstrated significantly higher environmental activity than the Fe/C NPs on eosin Y, a model halogenated organic pollutant. The environmental activity of the Fe/C/Pd NPs also increased with their increasing Pd content.