High-entropy alloys are equiatomic, multi-element systems that can crystallize as a single phase, despite containing multiple elements with different crystal structures. A rationale for this is that the configurational entropy contribution to the total free energy in alloys with five or more major elements may stabilize the solid-solution state relative to multiphase microstructures. We examined a five-element high-entropy alloy, CrMnFeCoNi, which forms a single-phase face-centered cubic solid solution, and found it to have exceptional damage tolerance with tensile strengths above 1 GPa and fracture toughness values exceeding 200 MPa.m(1/2). Furthermore, its mechanical properties actually improve at cryogenic temperatures; we attribute this to a transition from planar-slip dislocation activity at room temperature to deformation by mechanical nanotwinning with decreasing temperature, which results in continuous steady strain hardening.