This paper presents the strength (UCS) and ultrasonic pulse velocity (UPV) properties of cemented paste backfill (CPB) produced from two different mill tailings (Tailings T1 and T2). A total of 240 CPB samples with diameter x height of 5 x 10 cm and 10 x 20 cm prepared at different binder dosages (5-7 wt.%) and water-to-cement ratios (3.97-5.10) were subjected to the UPV and UCS tests at 7, 14, 28 and 56-days of curing periods. UCS and UPV of CPB samples increased with increasing the binder dosage and reducing the w/c ratio irrespective of the sample size and tailings type. CPB samples with a diameter x height of 5 x 10 cm were observed to produce consistently higher (up to 1.69-fold) UCSs than those of 10 x 20 cm CPB samples at all binder dosages and w/c ratios. However, at the corresponding binder dosages and w/c ratios, the maximum variation of UPV between the CPB samples of 5 x 10 cm and 10 x 20 cm was only 7.45%. Using the method of least squares regression, the UCS values were correlated with the UPV values for CPB samples of 10 x 20 cm in size. A linear relation with a high correlation coefficient appeared to exist between the UCS and UPV for CPB samples. These findings suggest that the UPV is essentially independent of the sample size. In this regard, the UPV test can be suitably exploited for the rapid estimation of the strength and quality of CPB samples even using small samples with concomitant benefits of reducing sample size. (C) 2013 Elsevier B. V. All rights reserved.