The research of the failure theory and criterion is the foundation of the frozen soil fracture mechanics. Considered the cementation stress and the defects inner the frozen soil and based on the elastic-plastic fracture mechanics theory, the nonlinear fracture failure process criterion is established. The nonlinear fracture factors and nonlinear fracture toughness are discussed and then the cementation stress crack model of nonlinear fracture failure of frozen soil is presented, especially for the tensile failure mode and compression failure mode. The semi-analytical finite element method is used to compute the nonlinear fracture factors and simulate the fracture failure process of the frozen soil.