Conducting polymers for battery applications have been subject to numerous investigations during the last two decades. However, the functional charging rates and the cycling stabilities have so far been found to be insufficient for practical applications. These shortcomings can, at least partially, be explained by the fact that thick layers of the conducting polymers have been used to obtain sufficient capacities of the batteries. In the present letter, we introduce a novel nanostructured high-surface area electrode material for energy storage applications composed of cellulose fibers of algal origin individually coated with a 50 nm thin layer of polypyrrole. Our results show the hitherto highest reported charge capacities and charging rates for an all polymer paper-based battery. The composite conductive paper material is shown to have a specific surface area of 80 m(2) g(-1) and batteries based on this material can be charged with currents as high as 600 mA cm(-2) with only 6% loss in capacity over 100 subsequent charge and discharge cycles. The aqueous-based batteries, which are entirely based on cellulose and polypyrrole and exhibit charge capacities between 25 and 33 mAh g(-1) or 38-50 mAh g(-1) per weight of the active material, open up new possibilities for the production of environmentally friendly, cost efficient, up-scalable and lightweight energy storage systems.