Powering the future, while maintaining strong socioeconomic growth and a cleaner environment, is going to be one of the biggest challenges faced by mankind nowadays. Thus, there is a transition from the use of fossil fuels to renewable energy sources. Cellulose, the main component of paper, represents a unique type of bio-based building blocks featuring exciting properties: low-cost, hierarchical fibrous structures, hydrophilicity, biocompatible, mechanical flexibility, and renewability, which make it perfect for use in paper-based sustainable energy storage devices. This review focuses on lithium-ion battery application of celluloses with cellulose at different scales, i.e., cellulose microfibers, and nanocellulose, and highlights the new trends in the field. Recent advances and approaches to construct high mass loading paper electrodes toward high energy density batteries are evaluated and the limitations of paper-based cathodes are discussed. This will stimulate the use of natural resources and thereby the development of renewable electric energy systems based on sustainable technologies with low environmental impacts and carbon footprints.