An improved hydrogen storage medium in the form of a fabric (124, 504, 704) comprises a yarn (300, 400) that includes carbon nanofibers or carbon nanotubes (302, 404) and elastomeric fibers (304, 402). The fabric (124, 504, 704) is a volume efficient arrangement of the carbon nanofibers or carbon nanotubes (302, 404) and is consequently characterized as a high density energy storage medium. According to a preferred embodiment a hydrogen storage device (100) comprises a flexible container (104) that includes the fabric (124). The flexibility of the container (104) in combination with the flexibility of the fabric (124) allows the hydrogen storage device 100 to be accommodated in irregularly shaped spaces. According to an embodiment of the invention a battery (700) uses the fabric (704) as a hydrogen storing anode.