An efficient method is presented for preparing hierarchical catalysts composed of multi-walled carbon nanotubes (MWCNTs) and Pd@CeO2 core-shell nanoparticles. These materials were then examined for the water gas shift reaction (WGSR), which demonstrated intimate contact between the constituent parts. The integration of the carbonaceous support improves the stability of the nanoparticles by ordering the dispersion of the inorganic phase and increases the activity by suppressing the deactivation of the active phase that is commonly observed in conventional Pd-CeO2 under reducing conditions, e.g. WGSR conditions. An optimum MWCNTs:Pd@CeO2 ratio exists that affords totally homogeneous structures and provides the best catalytic properties.