Electrospun PAN nanofibers were carbonized with or without iron(III) acetylacetonate to induce catalytic graphitization within the range of 900–1500°C, resulting in ultrafine carbon fibers with the diameter of about 90–300 nm. The structural properties and morphologies of the resulting carbon nanofibers were investigated using XRD, Raman IR, SEM, TEM, and surface area/pore analysis. The PAN-based carbon nanofibers carbonized without a catalyst had amorphous structures, with d002 = 0.37 nm, and smooth surfaces with very low surface areas of 22–31 m2/g. The carbonization of PAN-based nanofibers in the presence of the catalyst produced the graphite nanofibers (GNF) with d002 = 0.341 nm, indicating turbostrate structures. The graphite structures were grown by increasing the catalyst contents and the carbonization temperature. The hydrogen storage capacities of the aforementioned carbon nanofiber materials were evaluated through the gravimetric method using Magnetic Suspension Balance (MSB) at room temperature and at 100 bars. The storage data were obtained after the buoyancy correction. The CNFs showed hydrogen storage capacities of 0.16–0.50 wt.%, increasing with the increase of carbonization temperature, but that of the CNF at 1500°C was lowest. The hydrogen storage capacities of the GNFs with low surface areas of 100–250m2/g were 0.14–1.01 wt%.