Lightweight materials that are both highly compressible and resilient under large cyclic strains can be used in a variety of applications(1-8). Carbon nanotubes offer a combination of elasticity, mechanical resilience and low density(9), and these properties have been exploited in nanotube-based foams(10-14) and aerogels(15,16). However, all nanotube-based foams and aerogels developed so far undergo structural collapse(15) or significant plastic deformation with a reduction in compressive strength(10,11,13,14) when they are subjected to cyclic strain. Here, we show that an inelastic aerogel made of single-walled carbon nanotubes can be transformed into a superelastic material by coating it with between one and five layers of graphene nanoplates. The graphene-coated aerogel exhibits no change in mechanical properties after more than 1x10(6) compressive cycles, and its original shape can be recovered quickly after compression release. Moreover, the coating does not affect the structural integrity of the nanotubes or the compressibility and porosity of the nanotube network. The coating also increases Young's modulus and energy storage modulus by a factor of similar to 6, and the loss modulus by a factor of similar to 3. We attribute the superelasticity and complete fatigue resistance to the graphene coating strengthening the existing crosslinking points or 'nodes' in the aerogel.