To seek new potential materials for hydrogen storage, an arc-discharge method was employed to prepare nanosized nickel(or cobalt)/graphite composites, in which the nickel (or cobalt) particles were highly dispersed in a carbon matrix with particle size between 20 and 70 nm (or 5-20 nm). Quantitative TPD measurements showed that at about 500 °C and 30-50 atm these nanosized composites could uptake up to 2.8 wt % H2, which can be released at 500 °C and 1 atm. The addition of Ni (or Co) in C was found to largely enhance the H2 adsorption, with the optimal amount of Ni being 20 wt %. In-situ FTIR showed that hydrogen was dissociatively adsorbed only in the presence of a transition metal and bonded to carbon atoms forming C-H bond. The hydrogen adsorption/desorption could be recycled. However, the capacity decreased to 1.6 wt % after 5 cycles. TEM, XPS, and BET surface-area and pore-volume measurements revealed that some of the transition metal particles migrated out from the carbon matrix and agglomerated after the H2 adsorption/desorption cycles, which may reduce the transition metal-carbon synergism and thus the H2 storage capacity. Under low temperatures below -120 °C and moderate pressures above 6 atm hydrogen storage by these Ni(or Co)/C composites could be detected. Storage capacity up to 2.7 wt % for Ni/C was measured by PCI at 77 K and 70 atm.