A four-fold increase in palladium (Pd) mass-based hydrodesulfurization (HDS) activity was achieved by depositing Pd species as nanosized islands on 12 nm colloidal iron oxide (FeOx) nanoparticles via the galvanic exchange reaction. The highest palladium dispersion was obtained at an optimal Pd/Fe molar ratio of 0.2, which decreased when the ratio increased. The improved dispersion was responsible for the enhanced catalytic activity per the total Pd amount in the HDS of 4,6-dimethyldibenzothiophene at 623 K and 3 MPa as compared to the iron-free Pd/Al2O3 catalyst. The lattice strain and modified electronic properties of the Pd islands suppressed deep hydrogenation to dimethylbicyclohexyl and changed the hydrocracking product distribution. Pd nanoparticles deposited on commercial Fe2O3 did not provide such an activity enhancement and catalyzed significant cracking. This study demonstrates that FeOx@Pd structures are a possible alternative to monometallic Pd catalysts with enhanced noble metal atom efficiency for ultra-deep HDS catalysis and points to their great potential to reduce the catalyst cost and move towards more earth-abundant catalytic materials. © 2018 Reproduced by permission of the Royal Society of Chemistry.