Tissues and cells sustain recurring mechanical loads that span a wide range of loading amplitudes and timescales as a consequence of exposure to blood flow, muscle activity, and external impact. Both tissues and cells derive their mechanical strength from fibrous protein scaffolds, which typically have a complex hierarchical structure. In this study, we focus on a prototypical hierarchical biomaterial, fibrin, which is one of the most resilient naturally occurring biopolymers and forms the structural scaffold of blood clots. We show how fibrous networks composed of fibrin utilize irreversible changes in their hierarchical structure at different scales to maintain reversible stress stiffening up to large strains. To trace the origin of this paradoxical resilience, we systematically tuned the microstructural parameters of fibrin and used a combination of optical tweezers and fluorescence microscopy to measure the interactions of single fibrin fibers for the first time, to our knowledge. We demonstrate that fibrin networks adapt to moderate strains by remodeling at the network scale through the spontaneous formation of new bonds between fibers, whereas they adapt to high strains by plastic remodeling of the fibers themselves. This multiscale adaptation mechanism endows fibrin gels with the remarkable ability to sustain recurring loads due to shear flows and wound stretching. Our findings therefore reveal a microscopic mechanism by which tissues and cells can balance elastic nonlinearity and plasticity, and thus can provide microstructural insights into cell-driven remodeling of tissues.