The cytoskeleton is a highly adaptive network of filamentous proteins capable of stiffening under stress even as it dynamically assembles and disassembles with time constants of minutes. Synthetic materials that combine reversibility and strain-stiffening properties remain elusive. Here, strain-stiffening hydrogels that have dynamic fibrous polymers as their main structural components are reported. The fibers form via self-assembly of bolaamphiphiles (BA) in water and have a well-defined cross-section of 9 to 10 molecules. Fiber length recovery after sonication, H/D exchange experiments, and rheology confirm the dynamic nature of the fibers. Cross-linking of the fibers yields strain-stiffening, self-healing hydrogels that closely mimic the mechanics of biological networks, with mechanical properties that can be modulated by chemical modification of the components. Comparison of the supramolecular networks with covalently fixated networks shows that the noncovalent nature of the fibers limits the maximum stress that fibers can bear and, hence, limits the range of stiffening.