Metal and metal-oxide nanoparticles (NPs) are promising catalysts for dye degradation in wastewater treatment despite the challenges of NP recovery and recycling. In this study, water-dispersible NP superstructures with spherical morphology were constructed from hydrophobic Pd and Fe3O4 NPs by virtue of the oil droplets in an oil-in-water microemulsion as templates. Control of the evaporation rate of organic solvents in the oil droplets produces solid, hollow, and bowl-like superstructures. The component Fe3O4 and in particular Pd NPs can catalyze H2O2 degradation to create hydroxyl radicals and therewith degrade various dyes, and the magnetic Fe3O4 NPs also permit recycling of the superstructures with a magnet. Because the hollow and bowl-like superstructures increase the contact area of the NPs with their surroundings in comparison to solid superstructures, the catalytic activity is greatly enhanced. To improve the structural stability, the superstructures were further enveloped with a thin polypyrrole (PPy) shell, which does not weaken the catalytic activity. Because the current method is facile and feasible to create recyclable catalysts, it will promote the practicability of NP catalysts in treating industrial polluted water.