The fracture properties of a high-strength steel with a body-centered cubic (bcc) crystal structure have been characterized at -196 °C by performing tensile tests with different specimen geometries, three-point bending tests using Charpy specimens, and fracture mechanics tests, covering a broad range of stress states under quasi-static conditions. Both strength and ductility of the bcc steel are significantly increased when the temperature is decreased from room temperature to -196 °C. Enormous plasticity occurs in the material during tensile tests using various specimens at -196 °C, while macroscopic brittle fracture takes place in high triaxiality scenarios. A stress state dependence of ductile to brittle transition properties is observed, as the failure mechanisms at -196 °C change from cleavage fracture to shear failure with decreasing stress triaxiality. A unified stress-state-dependent fracture criterion, which considers the transition of failure mechanisms, is proposed to describe the fracture properties of similar bcc materials at cryogenic temperatures. The threshold triaxiality at which the transition of failure mechanisms takes place is a material property that is determined by the strain hardening capacity and fracture strength. In addition, a probabilistic formulation relying on the extreme value distribution has been incorporated into the model to render the statistical nature of cleavage fracture.