Self-assembly of graphene oxide (GO) nanosheets into porous 3D sponges is a promising approach to exploit their capacity to adsorb contaminants while facilitating the recovery of the nanosheets from treated water. Yet, forming mechanically robust sponges with suitable adsorption properties presents a significant challenge. Ultra-strong and highly porous 3D sponges are formed using GO, vitamin C (VC), and cellulose nanocrystals (CNCs) - natural nanorods isolated from wood pulp. CNCs provide a robust scaffold for the partially reduced GO (rGO) nanosheets resulting in an exceptionally stiff nanohybrid. The concentration of VC as a reducing agent plays a critical role in tailoring the pore architecture of the sponges. By using excess amounts of VC, a unique hierarchical pore structure is achieved, where VC grains act as soft templates for forming millimeter-sized pores, the walls of which are also porous and comprised of micron-sized pores. The unique hierarchical pore structure ensures the interconnectivity of pores even at the core of large sponges as evidenced by micro and nano X-ray computed tomography. The unique pore architecture translates into an exceptional specific surface area for adsorption of a wide range of contaminants, such as dyes, heavy metals, pharmaceuticals and cyanotoxin from water.