Nano-sized nickel particles were dispersed on multi-walled carbon nanotubes (MWCNTs) via an improved electroless deposition route using a supercritical CO2 fluid. The microstructure, chemical composition and crystallinity of the Ni-decorated CNTs were examined using a transmission electron microscope (TEM), an X-ray energy dispersive spectrometer (EDS), and an X-ray diffractometer (XRD), respectively. The analytical results indicate that, with assistance of the supercritical fluid, Ni nanoparticles with a diameter of approximately 10 nm can be uniformly dispersed on the surface of CNTs. The hydrogen storage capacity of the Ni-decorated CNTs was evaluated with a high-pressure microbalance at room temperature and under a hydrogen pressure of 6.89 MPa. The measured hydrogen adsorption amount of the Ni/CNTs nanocomposite was 1.06 wt%, which was much higher than 0.33 wt% found for the plain CNTs.