Nanostructured graphite was prepared by mechanical milling under a hydrogen atmosphere. Several samples obtained after different milling times were systematically examined to get fundamental information about the structures, hydrogen concentrations, and also hydrogen desorption properties. The hydrogen concentration reaches up to 7.4 mass% (CH0.95) after milling for 80 h, and two desorption peaks of hydrogen molecule (mass-number=2), starting at about 600 K and 950 K respectively, are observed inthermaldesorption mass-spectroscopy in the sample. Below the temperature of the second desorption peak, at which recrystallization related desorption occurs, the nanostructured graphite is expected to retain its specific defective structures mainly with carbon dangling bonds as suitable trapping sites for hydrogen storage.