The fracture properties of hydrogels which present similar characteristics to the Mullins effect is expected to decrease under repeated cyclic loading. Therefore, we assessed how cyclic loading affects the fracture behavior, the distribution of strain fields and the microstructure of hydrogel composites reinforced with nano-fibrillated cellulose fibers. Surprisingly, we observed that preloading before the creation of a crack in the hydrogel composite increased the fracture strength of pre-notched samples, while the corresponding fracture energy decreased. To understand this behavior, a digital image correlation analysis at the macro- and microscopic scale was performed to obtain local information on the strain field. In addition, the morphology of cellulose fibers was directly observed through fluorescence confocal microscopy before and after cyclic loading at different maximal applied strains. Microscopy results show that cyclic loading re-arrange the fiber network and relax local residual stresses in the hydrogel composite. The re-arrangement of the fiber network decreases the overall elastic modulus and correspondingly the fracture energy. However, this phenomenon helps the hydrogel composite to accommodate larger strains before the crack starts to propagate, which subsequently improves the fracture strength of pre-notched samples.