The efforts on deep sea exploration and development have posed many challenges on the corrosion resistance and safety use of high strength steel in recent years. This has attracted a lot of attentions on the corrosion behavior of high strength steel in deep sea environment. Hydrostatic pressure has been identified as one of the most significant factors that affect pitting corrosion of materials or steel structures used in deep sea. However, pre-stress introduced by the actual service conditions is probably another critical factor of deep sea corrosion. The purpose of this work is to investigate the corrosion behavior of a new type Ni-Cr-Mo-V high strength steel under the combined stresses of hydrostatic pressure and preloaded tensile stress in simulated deep-sea environment. Corrosion rate measurement, SEM observation, statistical analysis of pitting geometry and finite element (FE) analysis were used in this work. The results indicated that corrosion rate of Ni-Cr-Mo-V high strength steel increased with the increase of hydrostatic pressure and pre-stress. The deterioration of corrosion resistance of the steel mainly reflected in pit initiation, pit growth and pit coalescence. Rather than pre-stress, hydrostatic pressure exhibited obvious effect on promoting pit initiation. Pits initiated in the form of corrosion pin-holes, which randomly distributed at the corroded surface. Both hydrostatic pressure and pre-stress facilitated pit growth, and there was an interaction between them, which was more remarkable at higher pre-stress. Hydrostatic pressure was mainly responsible for pit growth parallel to the steel surface, while pre-stress was essential to pit depth increase. Adjacent pits were inclined to coalesce in the direction perpendicular to pre-stress. With the increase of hydrostatic pressure and pre-stress, the aspect ratio of pits increased, which can lead to the formation of uniform corrosion.