Cold rolled super duplex stainless steel (SDSS) were subjected to recovery (300 °C) and recrystallization (1020 °C) annealing. Annealing related microstructural changes were quantified with microtexture and phase-specific micro-hardness. Subsequent electrochemical characterization included potentiodynamic anodic polarization tests and Mott-Schottky analysis. It was established, for both single and two-phase specimens, that extensive recovery did not affect the electrochemical behavior, while the shortest recrystallization led to significant improvements in corrosion resistance. Improvements in corrosion performance of cold rolled SDSS was thus possible only through recrystallization, and associated removal of large lattice curvatures in the metallic substrate and reduced defect densities in the protective oxide film.