The aim of the study was to evaluate the corrosion properties of three different grades of high-speed steel following a heat treatment procedure involving deep cryogenic treatment after quenching and to investigate how these properties are connected to the microstructure and hardness of the material. The hardness of steels was measured, and microstructural properties were determined through observation of the metallographically prepared steels using scanning electron microscopy. These studies were complemented corrosion evaluation by the use of corrosion potential measurement and linear polarization measurement of steels in a sodium tetraborate buffer at pH 10. The results showed that the deep cryogenic procedure of high-speed steel changed the microstructure and consequently affected the hardness of the investigated steels to different extents, depending on their chemical composition. Corrosion studies have confirmed that some high-speed steels have improved corrosion properties after deep cryogenic treatment. The most important improvement in corrosion resistance was observed for deep cryogenically treated high-speed steel EN 1.3395 (M3:2) by 31% when hardened to high hardness values and by 116% under lower hardness conditions. The test procedure for differentiating corrosion properties of differently heat-treated tool steels was established alongside the investigation.