Abstract: Tailing-cemented backfill is a cement-based heterogeneous composite whose uniaxial compressive strength (UCS) and ultrasonic pulse velocity (UPV) are dependent on cement dosage, solid content, sample type, etc. In this paper, uniaxial compressive test and ultrasonic pulse velocity test of three types of backfill samples (7.07 cm×7.07 cm×7.07 cm cube, Φ5 cm×10 cm cylinder and Φ7 cm×14 cm cylinder) were performed, and the effects of cement dosage, solid content and sample type on the backfill strength and ultrasonic pulse velocity were investigated by grey correlative degree analysis. The results show that cement dosage is the key to the backfill strength with a correlative degree of 0.837, while the ultrasonic pulse velocity is mostly influenced by solid content with a correlation degree of 0.712. An exponential prediction relation between UCS and UPV and a BP neural network prediction model were built, and they were validated by F-test and t-test of statistical analysis, respectively. The methods proposed can be new approaches for predicting the backfill strength.