Supercritical carbon dioxide (scCO2) fluid is used to decorate multi-walled carbon nanotubes (CNTs) with palladium (Pd) nanoparticles. Pd(II) hexafluoroacetylacetonate (Pd(hfa)2) is dissolved in scCO2 as a metal precursor. Electrochemical reduction of the Pd(II) is executed by dimethyl amineborane (DMAB). Owing to the high diffusivity, near-zero surface tension, and low viscosity of the scCO2 fluid, the deposited Pd nanoparticles are uniformly dispersed and tightly anchored on the surface of CNTs. The microstructure, chemical composition, and crystallinity of the prepared Pd/CNTs nano-composites are characterized with a transmission electron microscope (TEM), an X-ray energy dispersive spectroscope (EDS), and an X-ray diffractometer (XRD), respectively. The experimental results indicate that the size and the amount of Pd particles on CNTs can be manipulated by adjusting the precursor concentration. Moreover, hydrogen storage capability of the Pd/CNTs composite, evaluated with a high-pressure microbalance (at 6.89 MPa and 25°C), is 1.31 wt %, which is approximately four times higher than that (0.33 wt%) of pristine CNTs.