In the present work, the Fe-13Mn-8Al-(0.7, 1.2)C steels were subjected to different post-cold rolling annealing treatments in a temperature range of 800–1000 °C for 15 min to investigate the microstructural evolution and the mechanical properties. Both steels annealed at 800 °C consisted of fine austenite and ferrite grains along with intergranular κ-carbides formed by eutectoid reaction, which contributed to the high strength but deteriorated ductility. With annealing temperature increasing, the volume fraction of ferrite and intergranular κ-carbides progressively decreased. Meanwhile, the precipitation of intragranular κ′-carbides enhanced the yield strength, whereas coarse austenite was harmful to both strength and elongation. The increase in C content increased the volume fraction of intergranular κ-carbides and austenite as well as retarded the austenite recrystallization, which further increased strength and strain hardening rate but deteriorate ductility. The deformation mechanism in austenite was massive planar slip. The microbands were widely observed in both steels at an annealing temperature above 900 °C.