The evolution of microstructure and mechanical properties of AISI 904L stainless steel subjected to high-pressure torsion (HPT) and post-deformation annealing was investigated. A nanocrystalline microstructure with an average grain size of 48 nm was obtained by HPT, showing an ultra-high strength of ∼2.2 GPa. However, a rather limited ductility in the tension experiment was observed, and necking started immediately after the elastic regime. Post-deformation annealing resulted in recrystallization, formation of σ-phase, and grain growth, where the best strength-ductility synergy (high strength of ∼1.5 GPa and total elongation of 24%) was obtained for the samples continuously annealed from room temperature up to 790 °C with an ultrafine-grained (UFG) microstructure (average grain size of 220 nm) and low amounts of the σ-phase.