The nano-sized carbon materials produced during the metal dusting process of 304L stainless steel were studied in this investigation. In the reaction atmosphere of CO/CO2 (35:1) mixed gas, the nanofibers and multi-wall carbon nano-tubes (MWCNTs) could be obtained at 500 °C and 600 °C, respectively. Hydrogen storage performance of the MWCNTs was evaluated by an electrochemical method; the experimental data indicated that their discharge capacity was 57 mAh/g. Two methods, including heat treatment and acid etching, were used to purify the as-prepared MWCNTs. It was found that the hydrogen storage capacity of the heat-treated and acid-treated MWCNTs was greatly improved to 85 mAh/g and 103 mAh/g, respectively. The considerable capacity increase of the etched MWCNTs was attributed to the elimination of the surface amorphous carbon and the coexisted metal particles.