Microstructure observations, thermal desorption spectroscopy (TDS) tests, hydrogen permeation measurements, electrochemical tests, and slow strain rate tensile (SSRT) tests are conducted investigate the beneficial effect of Nb microalloying on the stress corrosion cracking (SCC) behavior of high-strength low-alloy (HSLA) steels in a simulated deep-sea environment. The results show that the addition of Nb significantly decreases the SCC susceptibility of HSLA steel in a simulated deep-sea environment, and the role of Nb is attributed to microstructure optimization and the strong hydrogen-trap function of nanosized NbC precipitates with hydrogen activation energy up to 100.5 kJ mol−1. In the simulated deep-sea environment, the SCC resistance of HSLA steel is enhanced by microstructure optimization and the hydrogen-trap function via Nb microalloying, and both anodic dissolution (AD) and hydrogen embrittlement (HE) are weakened. Moreover, the improvement of SCC resistance of HSLA steel with a higher hydrogen concentration via Nb microalloying is more obvious, in which the decrease of hydrogen-induced anodic dissolution (HIAD) and HE effects is more distinct, and the strong hydrogen-trap effect of NbC precipitates is the predominant mechanism to improve SCC resistance.