Fibrous networks are ideal functional materials since they provide mechanical rigidity at low weight. Here, we demonstrate that fibrous networks of the blood clotting protein fibrin undergo a strong and irreversible increase in their mechanical rigidity in response to uniaxial compression. This rigidification can be precisely controlled by the level of applied compressive strain, providing a means to program the network rigidity without having to change its composition. To identify the underlying mechanism we measure single fiber–fiber interactions using optical tweezers. We further develop a minimal computational model of cohesive fiber networks that shows that stiffening arises due to the formation of new bonds in the compressed state, which develop tensile stress when the network is re-expanded. The model predicts that the network stiffness after a compression cycle obeys a power-law dependence on tensile stress, which we confirm experimentally. This finding provides new insights into how biological tissues can adapt themselves independently of any cellular processes, offering new perspectives to inspire the design of reprogrammable materials.