For decades, solid solution strengthening with up to 9 wt.% Ni has been the only successful strategy to obtain high strength and high impact toughness in bcc-structured (ferritic or tempered martensitic) cryogenic steels. Until now coherent nano-precipitates, an effective strengthening agent at room temperature, cannot be used to improve properties at cryogenic temperatures. Here, a new type of Mo-rich nano-B2 precipitates formed in a 6.5 wt.% Ni steel upon doping with 0.2 wt.% of Mo is reported. These precipitates are not only fully coherent with the matrix but are also shearable at 77 K. A high precipitate number density in excess of 2 × 10²⁴ m⁻³ has been achieved by an industrially feasible process optimization, which brings both the cryogenic strength and impact toughness of the steel to the same levels as those of 9Ni steels. The Mo-rich B2 precipitation strengthening, therefore, opens a new avenue for the design and development of low-cost high-performance cryogenic steels.