Metastable austenitic steels having ultrafine grained (UFG) microstructures can be fabricated by conventional cold rolling and annealing processes by utilizing the deformation-induced martensitic transformation during cold rolling and its reverse transformation to austenite upon annealing. However, such processes are not applicable when the austenite has high mechanical stability against deformation-induced martensitic transformation, since there is no sufficient amount of martensite formed during cold rolling. In the present study, a two-step cold rolling and annealing process was applied to an Fe-24Ni-0.3C metastable austenitic steel having high mechanical stability. Prior to the cold rolling, a repetitive subzero treatment and reverse annealing treatment were applied. Such a treatment dramatically decreased the mechanical stability of the austenite and greatly accelerated the formation of deformation-induced martensite during the following cold rolling processes. As a result, the grain refinement was significantly promoted, and a fully recrystallized specimen with a mean austenite grain size of 0.5 μm was successfully fabricated, which exhibited both high strength and high ductility.