A hydrogen storage alloy comprises a hydrogen storage base formed of a mixture of magnesium and an alloy, such as a magnesium-nickel alloy, a magnesium-titanium alloy, a magnesium-niobium alloy, a magnesium-manganese alloy, or a magnesium-cobalt alloy, and a catalytic layer covering a surface of the base. A hydrogen storage alloy unit includes the hydrogen storage base and a porous body including an assembly of nanofibers. The alloy may be vapor-deposited onto the assembly of nanofibers. The nanofibers may be tangled to provide spaces between the fibers for the passage of hydrogen molecules. The nanofibers in one example are also porous. A catalytic layer of platinum may cover a surface of the hydrogen storage base.