Abstract: Tailings consolidation discharge can effectively solve the problem of tailings disposal. However, the tailings pile after consolidation is mostly on the surface, and its performance is greatly affected by the natural environment. Freeze-thaw cycles are widespread in northern China. Freeze-thaw has a great influence on the strength, ultrasonic velocity, and electrical resistance characteristics of cemented mass. To explore the damage evolution state and mechanism of the cemented mass of unclassified tailings under freeze-thaw cycle, in this paper, a series of freeze-thaw tests on a cemented mass of unclassified tailings from the Lilou iron mine were performed. Then the cemented mass samples after different runs of freeze-thaw tests were used to conduct uniaxial compressive strength tests, scanning electron microscopy (SEM) test, resistivity test, and ultrasonic wave velocity test. Quantitative analysis of surface crack images of samples was performed using MATLAB-based binarized digital image processing technology, and a test method for joint testing of freeze-thaw cycle damage of cemented mass specimens using electrical resistivity (ER) and ultrasonic pulse velocity (UPV) testing techniques was proposed. The results indicate that the uniaxial compressive strength (UCS) decreases with increase in freeze-thaw cycles. The greatest decline is for the UCS of cemented mass subjected to 0–5 freeze-thaw cycles. The damage of the cemented mass in the freeze-thaw cycle is a gradual accumulation process. The development process of the apparent degradation characteristics of the cemented mass of unclassified tailings is as follows: micro-fracture initiation → fracture extension development → outer layer failure → internal structure failure; the higher the initial strength of the cemented mass, the fewer the number of surface cracks. The internal microstructure changes from dense to loose. The UCS of the cemented mass is positively correlated with the ER and the UPV, following the logarithmic function relationship, and the nondestructive testing models of UCS-ER and UCS-UPV are established. It is shown that the ER and UPV can accurately and comprehensively evaluate the damage state in cemented mass of unclassified tailings.