The role of grain size and strain rate on the corrosion behavior of plastically-deformed Ti-stabilized austenitic stainless steel (AISI 321) in saline media was investigated. The as-received coarse-grained alloy (CG: ~37 µm) was subjected to thermomechanical processing to develop fine (FG: ~3 µm) and ultrafine (UFG: ~0.24 µm) grained structures. These samples were deformed under high (dynamic) and low (quasi-static) strain-rate conditions to a similar true strain of ~0.86. Microstructural analyses on specimens after deformation prior to corrosion study suggests a shift from the estimated stacking fault energy value of the steel. Electrochemical tests confirm the highest corrosion resistance for UFG specimens due to the formation of the most stable adsorbed passive film. This is followed by FG and CG specimens in that order. For the three grain sizes, the corrosion resistance of specimen deformed under quasi-static loading condition is higher than that subjected to dynamic impact loading while the corrosion resistance of undeformed samples is the least. This work also confirms the non-detrimental effect of TiCs in AISI 321 austenitic stainless steel on its corrosion resistance. However, TiNs were observed to be detrimental by promoting pitting corrosion due to galvanic coupling of TiNs with their surrounding continuous phase. The mechanism of pitting in AISI 321 in chloride solution is proposed.