The aim of this study is to investigate the predictability of the uniaxial compressive strength (UCS) of cemented paste backfill (CPB) prepared from three different tailings (Tailings T1, Tailings T2 and Tailings T3) using ultrasonic pulse velocity (UPV) test. For this purpose, 180 CPB samples with diameter x height of 5 x 10cm (similar to NX size) prepared at different binder dosages and consistencies were subjected to the UPV and UCS tests at 7-56days of curing periods. The effects of binder dosage and consistency on the UPV and UCS properties of CPB samples were investigated and UCS values were correlated with the corresponding UPV data. Microstructural analyses were also performed on CPB samples in order to understand the effect of microstructure (i.e. total porosity) on the UPV data. The UPV and UCSs of CPB samples increased with increasing binder dosage and reducing the consistency irrespective of the tailings type and curing periods. Changes in the mixture properties observed to have a lesser extent on the UPV properties of CPB, while, their effect on the UCS of CPB was significant. Empirical equations were produced for each mixture in order to predict the UCSs of CPB through UPV. The validity of the equations was also checked by t- and F-test. The results showed that a linear relation appeared to exist between the UPV and UCS with high correlation coefficients (r0.79) and all models were valid by statistical analysis. Mercury intrusion porosimetry (MIP) and scanning electron microscope (SEM) analyses have revealed that the UPV properties of CPB samples were highly associated with their respective microstructural properties (i.e. total porosity). The major output of this study is that UPV test can be effectively used for a preliminary prediction of the strength of CPB.