One of the novel approaches for discogenic lower back pain treatment is to permanently replace the core of the intervertebral disc, so-called Nucleus Pulposus, through minimally invasive surgery. Recently, we have proposed Poly(Ethylene Glycol) Dimethacrylate (PEGDM) hydrogel reinforced with Nano-Fibrillated Cellulose (NFC) fibers as an appropriate replacement material. In addition to the tuneable properties, that mimic those of the native tissue, the surgeon can directly inject it into the degenerated disc and cure it in situ via UV-light irradiation. However, in view of clinical applications, the reliability of the proposed material has to be tested under long-term fatigue loading. To that end, the present study focused on the characterization of the fatigue behavior of the composite hydrogel and investigated the governing physical phenomena behind it. The results show that composite PEGDM-NFC hydrogel withstands the 10 million compression cycles at physiological condition. However, its modulus decreases by almost 10% in the first cycle and then remains constant, while cyclic loading does not affect the neat PEGDM hydrogel. The observed softening behavior has similar characteristics of the Mullins effect. It is shown that the reduction of modulus is due to the gradual change of NFC network, which is highly stretched in the swollen state. Moreover, the swelling degree of the matrix is correlated to the extent of softening during cyclic loading. Consequently, softening can be minimized by lowering the swelling of the composite hydrogel.