The nano-sized carbon materials (NCMs) in this study were produced during the metal dusting process. The relationship between material characteristics and the hydrogen storage performance was investigated. Morphology and crystallinity of the NCMs were observed with a scanning electron microscope and a transmission microscope. Moreover, the specific surface area, microstructure, and surface functional groups of the NCMs were examined by a surface area analyzer, a Raman spectrometer, and an X-ray absorption spectroscope, respectively. In addition, a high pressure thermal gravity analyzer was employed to measure the hydrogen storage capacity of the NCMs. The experimental results indicated that the reaction atmosphere and temperature significantly affected material characteristics of the obtained NCMs and thereby their hydrogen storage performance. The NCMs had a tubular structure with a high degree of crystallinity and high surface area were confirmed to possess superior hydrogen storage capability. It was also found that the more the surface functional groups existed the less amount of hydrogen could be adsorbed on the NCMs.