As a supplemental process of heat treatment, deep cryogenic treatment (DCT) is believed to have favorable effects on the mechanical properties of steels. In this study, three different sequences of DCT and tempering, including QCTT (Q: quenching, C: DCT, T: tempering), QTC, and QTCT, were investigated to discover an effective method to improve the impact toughness and fatigue life of a typical ultrahigh strength steel simultaneously. Compared with the traditional heat treatment process, the impact toughness, fracture elongation, and fatigue life were improved by 10%, 17.8%, and 13.7%, respectively, after the QTC treatment process. The microstructures were characterized by scanning electron microscope (SEM), electron backscatter diffraction (EBSD), transmission electron microscopy (TEM), and electron probe micro-analysis (EPMA). The results indicate that after QTC process, the formation of cracks was restricted due to the decrease of carbides and disappear of twinned martensite, both of which would serve as the sources of cracks. Besides, the propagation of cracks is hindered because the decrease of blocky retained austenite and increase of filmy retained austenite. As a result, the impact toughness, fracture elongation and fatigue life are improved simultaneously. This work provides a new and effective method to simultaneously improve the toughness and fatigue life of ultrahigh strength steels.