Structural materials used for safety critical applications require high strength and simultaneously high resistance against crack growth, referred to as damage tolerance. However, the two properties typically exclude each other and research efforts towards ever stronger materials are hampered by drastic loss of fracture resistance. Therefore, future development of novel ultra-strong bulk materials requires a fundamental understanding of the toughness determining mechanisms. As model material we use today's strongest metallic bulk material, namely, a nanostructured pearlitic steel wire, and measured the fracture toughness on micron-sized specimens in different crack growth directions and found an unexpected strong anisotropy in the fracture resistance. Along the wire axis the material reveals ultra-high strength combined with so far unprecedented damage tolerance. We attribute this excellent property combination to the anisotropy in the fracture toughness inducing a high propensity for micro-crack formation parallel to the wire axis. This effect causes a local crack tip stress relaxation and enables the high fracture toughness without being detrimental to the material's strength.