Nowadays, the cemented paste backfill mining method is widely used in mines. Since the temperature of the mine increases with increasing mining depth, the influence of temperature on the mechanical properties of cemented paste backfill (CPB) require attention. To address the problem of less research on paste performance in high temperature environments, uniaxial compressive strength tests of CPB at different temperatures were performed, and it was observed that temperature had a significant effect on the CPB strength. The CPB strength at a curing temperature above 40 °C deteriorated in the later curing time period, CPB at 65 °C was “crisp”, and the strength was lower than 40 °C in 3~28 days. Microscopic tests, such as thermogravimetric analysis (TGA/DTG), X-ray diffraction (XRD) and scanning electronic microscopy (SEM) analysis, of the samples found that the coarsening of the pore structure of CPB was the main reason for the decrease in the strength caused by the increase in temperature. The effect of curing temperature on the deformation characteristics of CPB was studied. Different curing temperatures had a greater impact on the stress-strain curve and elastic modulus, and there was a linear relationship between the elastic modulus and strength. Finally, based on MATLAB, a back propagation (BP) neural network model of strength under different curing temperature conditions was established. Compared with the actual value and the predicted value, the average absolute error was less than 0.2 MPa, and the average relative error was less than 6%. This prediction model had a high accuracy. The research results provide a good reference significance for the strength design of CPB.