Abstract: Improper drilling schemes may cause engineering problems such as wellbore collapse and wellhead subsidence during the drilling of permafrost. The research on mechanical evolution of deep frozen soil paves the way for construction design. In this paper, soil samples at different depths were remolded with the frozen soil from Mohe, and triaxial mechanical tests were carried out under different confining pressures and temperatures to analyze the characteristics of stress–strain curves of frozen soil under different conditions. The strength of frozen soil was statistically studied by multiple regression analysis, and the strength criterion for it was further established. The research results showed that the stress–strain curves of the frozen soil samples presented nonlinear deformation behavior on the whole. In its frozen state, soil strength was controlled mainly by temperature and confining pressure while it was dominated by confining pressure and soil depth in its non-frozen state. In addition, frozen soil strength was composed of the strength of soil skeleton and the cementing strength of ice in pores. The strength of soil skeleton satisfies the Mohr-Coulomb criteria, and the cohesion and internal friction angle increases with soil depth. The cementing strength of ice in pores grows with the decline of ambient temperature, and increases and then decreases as the confining pressure increases. On this basis, the strength criterion for Mohe frozen soil was established, and the verification results proved that it can well characterize the strength distribution of Mohe frozen soil in the melt and frozen state.