Many applications proposed for graphene require multiple sheets be assembled into a monolithic structure. The ability to maintain structural integrity upon large deformation is essential to ensure a macroscopic material which functions reliably. However, it has remained a great challenge to achieve high elasticity in three-dimensional graphene networks. Here we report that the marriage of graphene chemistry with ice physics can lead to the formation of ultralight and superelastic graphene-based cellular monoliths. Mimicking the hierarchical structure of natural cork, the resulting materials can sustain their structural integrity under a load of >50,000 times their own weight and can rapidly recover from >80% compression. The unique biomimetic hierarchical structure also provides this new class of elastomers with exceptionally high energy absorption capability and good electrical conductivity. The successful synthesis of such fascinating materials paves the way to explore the application of graphene in a self-supporting, structurally adaptive and 3D macroscopic form.