An energy storage device structure comprises a first electrode layer, an electrolyte layer and a second electrode layer. At least one of the electrode layers comprise a metallic base layer, a layer of carbon nanotubes grown on the base layer and a layer of carbon nanoparticles disposed on the carbon nanotube layer, the carbon nanoparticle layer being arranged to face the electrolyte layer. The structure has much larger width and length than thickness, so it is rolled up or folded and then hermetically sealed to form an energy storage unit. The layer of carbon nanotubes is grown on the metallic base layer by a chemical vapor deposition process at a temperature no higher than 550° C. The carbon nanotubes in the carbon nanotube layer are at least partially aligned in a direction that is perpendicular to the surface of the metallic base layer.