Viscoelasticity plays an important role in the mechanical behavior of biological tissues undergoing dynamic loading. Exploring viscoelastic relaxation spectra of the tissue is essential for predicting its mechanical response. Most load-bearing tissues, however, are also composed of networks of intertwined fibers and filaments of, e.g., collagen, elastin. In this work, we show how non-affine deformations within fiber networks affect the relaxation behavior of the material leading to the emergence of structure-dependent time scales in the relaxation spectra. In particular, we see two different contributions to the network relaxation process: a material contribution due to the intrinsic viscoelasticity of the fibers, and a kinematic contribution due to non-affine rearrangement of the network when different fibers relax at different rates. We also present a computational model to simulate viscoelastic relaxation of networks, demonstrating the emergent time scales and a pronounced dependence of the network relaxation behavior on whether components with different relaxation times percolate the network. Finally, we observe that the simulated relaxation spectrum for Delaunay networks is comparable to that measured experimentally for reconstituted collagen gels by others. STATEMENT OF SIGNIFICANCE: Viscoelasticty plays an important role in the mechanical behavior of biological tissues undergoing dynamic loading. Stress relaxation tests provide a convenient way to explore the viscoelastic behavior of the material, while providing an advantage of interrogating multiple time scales in a single experiment. Most load bearing tissues, however, are composed of networks of intertwined fibers and filaments. In the present study, we analyze how the network structure can affect the viscoelastic relaxation behavior of a tissue leading to the emergence of structure-based time scales in the relaxation spectra.