Structural components subject to cyclic stress can succumb to fatigue, causing them to fail at stress levels much lower than if they were under static mechanical loading. However, despite extensive research into the mechanical properties of carbon nanotube structures for more than a decade, data on the fatigue behaviour of such devices have never been reported. We show that under repeated high compressive strains, long, vertically aligned multiwalled nanotubes exhibit viscoelastic behaviour similar to that observed in soft-tissue membranes. Under compressive cyclic loading, the mechanical response of the nanotube arrays shows preconditioning, characteristic viscoelasticity-induced hysteresis, nonlinear elasticity and stress relaxation, and large deformations. Furthermore, no fatigue failure is observed at high strain amplitudes up to half a million cycles. This combination of soft-tissue-like behaviour and outstanding fatigue resistance suggests that properly engineered nanotube structures could mimic artificial tissues, and that their good electrical conductivity could lead to their use as compliant electrical contacts in a variety of applications.