As lots of underground mines have been exploited in the past decades, many stope instability and surface subsidence problems are appeared in the underground mines, while the cemented paste backfill (CPB) technology has been applied for more than 40 years, and it can solve these problems. As it is shown that the effect of backfilling is mainly affected by the mechanical properties of the CPB, and there are lots of factors which can influence the strength of the CPB, but the coupled effects of curing conditions has not been reported. In this research, the coupled effects of curing conditions are importantly considered, and the uniaxial compressive strength (UCS) is adopted as the important evaluation index of CPB, then the evolution law of the UCS for CPB are analyzed, also the mathematical strength model of CPB is established. The findings suggest that the relationship between the UCS of CPB and curing stress develops the function of quadratic polynomial with one variable, while the UCS of the CPB shows the power function as the curing temperature increases. Moreover, the established mathematical strength model is verified on the basis of laboratory experiments, the error between the measured UCS and the prediction UCS is less than 15%. It shows that the established strength model of the CPB by considering the curing conditions can predict the UCS very well, it has great significance for the safety design of CPB.