The theory of damping is discussed in Newton's Principia and has been tested in objects as diverse as the Foucault pendulum, the mirrors in gravitational-wave detectors and submicrometre mechanical resonators. In general, the damping observed in these systems can be described by a linear damping force. Advances in nanofabrication mean that it is now possible to explore damping in systems with one or more atomic-scale dimensions. Here we study the damping of mechanical resonators based on carbon nanotubes and graphene sheets. The damping is found to strongly depend on the amplitude of motion, and can be described by a nonlinear rather than a linear damping force. We exploit the nonlinear nature of damping in these systems to improve the figures of merit for both nanotube and graphene resonators. For instance, we achieve a quality factor of 100,000 for a graphene resonator.