The curing temperature-dependent cement hydration causes the nonlinear evolution of fracture behavior and properties of fiber-reinforced cemented paste backfill (CPB) and thus influences the stability of mine backfill materials in deep mines. Therefore, the coupled effect of curing temperature (20, 35, and 45 °C) and cement hydration at different curing times (3, 7, and 28 d) on the mode-I and mode-II fracture behavior and properties of fiber-reinforced CPB is investigated. A comprehensive experimental testing program consisting of semicircular bend tests, direct shear tests, measurement of volumetric water content and matric suction, TG/DTG tests, and SEM observation is carried out. The results show that the coupled thermochemical effect results in strongly nonlinear development of pre- and post-peak behavior of fiber-reinforced CPB. Moreover, the results discover a positive linear correlation between fracture toughness and shear strength parameters and also reveal the vital role played by matric suction in the formation of fracture toughness. Furthermore, predictive functions are developed to estimate the coupled thermochemical effect on the development of K_Ic and K_IIc. Therefore, the findings and the developed mathematical tools have the potential to promote the successful application of fiber-reinforced CPB technology in deep underground mines.