Alumina-forming austenitic (AFA) steel is expected to be applied to high-temperature components of ultra-supercritical thermal power plants. However, the high-temperature strength and stability of AFA steel need to be improved further. Here, the influence of pre-aging on the precipitation behavior, microstructural evolution, and mechanical properties of cold-rolled AFA steel was investigated. The results showed that pre-aging significantly influences the synergistic strengthening due to dislocations and precipitation in cold-rolled AFA steel during the process of high-temperature aging treatment. The precipitates in a sample that received pre-aging treatment exhibited strong pinning effect on grain boundaries and dislocations, which enhances the effect of precipitation strengthening by boosting the number of nucleation sites and the driving force for the formation of the precipitates. Compared to cold rolling with a 10% thickness reduction but without pre-aging, the formation of the Laves phase and the B2-NiAl phase after pre-aging for 24 h resulted in increased pinning on the dislocations and grain boundaries, which prevented dislocation slip, generated stress concentrations, boosted the number of nucleation sites and the driving force for the formation of the precipitates, and accelerated the phase-transition process; the volume fraction of the precipitates also increased significantly. Hardness and tensile tests at room temperature showed that the strength and hardness resulting from both cold rolling and cold rolling after pre-aging first increased and subsequently decreased.