This paper presents the findings of a research study designed and conducted to investigate the effects of mineral admixture and curing temperature on uniaxial compressive strength (UCS) and ultrasonic pulse velocity (UPV) behavior of laboratory-prepared cemented paste backfill (CPB) samples. A total of 290 CPB samples were prepared at different replacement rates (10-80%), cured at various temperatures (10-50 degrees C), and respectively subjected to both UPV and UCS testing after curing times of 3, 7, 14, 28, 56 and 90 days. The obtained experimental results show that the addition of fly ash (FA) can lead to an increase or decrease trend in UCS and UPV behavior of CPB samples, depending on the replacement level of admixtures. There is a competition between the strength-increasing factor (micro-filler effect of FA) and strength-decreasing factor (lower amount of cement hydration products induced by replacement ratio). Both UPV and UCS are found to decrease with increasing blast furnace slag (Slag) replacement level mainly attributable to its low pozzolanic reactivity. Besides, the curing temperature has a significant influence on UCS and UPV behavior, depending on the curing time. Results also suggest that UPV is less sensitive to the variation in the admixture dosage and curing temperature than UCS. As a result, there exists a clear linear relationship between UPV and UCS behavior of both CPB samples prepared with FA and/or Slag admixtures, and CPB samples tested at each curing temperature. The main findings of this research study suggest that the UPV test can be reliably used for predicting CPB's strength properties, saving money and time to mine operators.