A facile displacement reaction is proposed for decorating multi-walled carbon nanotubes (CNTs) with nanoparticles. The redox couple is used as an example; the Sn(II) pre-treated CNTs reacted with Pd(II)-containing solution to produce a Pd/CNT composite. The two-step process, with the aid of ultrasonication, can produce nano-sized particles that are uniformly dispersed and tightly anchored on the surfaces of CNTs. The proposed synthesis protocol does not need sophisticated equipment, making it low-cost. Large-scale production should be realizable. The constructed heterostructure exhibits a synergistic effect in its hydrogen storage performance, which was evaluated using a high-pressure microbalance. The deposited Pd-based nanoparticles enhanced the spillover reaction on CNTs, doubling the amount of hydrogen adsorbed at room temperature as compared to pristine CNTs.