The effect of addition of Ta and Zr on the evolution of the second phase precipitation and microhardness of Fe-Cr-Al-Mo-Nb alloys was investigated. For this purpose, a series of alloy ingots were prepared by vacuum arc melting in high purity Ar gas and homogenized at 1473 K/2 h. After solid solution treatment, the four ingots were hot rolled to produce plates, which then were annealed at 1473 K for 10 min, and then warm rolled successively at 1073 K and 873 K to obtain metal sheets of 2 mm thick, followed by aging treatment at 873 K/24 h and heat treatment at different temperatures. After the final heat treatments, the alloy sheets were characterized by means of XRD, OM, SEM, and EPMA. while their mechanical property was examined by material testing machine. The results show that the aging alloys are mainly composed of two Laves phases with different sizes, and the addition of Zr promoted the precipitation of fine particles, while inhibited the precipitation of coarse particles. With the increase of the heat treatment temperature, the second phase particles are significantly coarsened and redissolved. After heat treatment at 1473 K/1 h, the Zr and Ta/Zr modified alloys exhibited high microstructural stability, but significantly inhibited the re-solvation of the second phase particles, thereby resulted in that the two alloys presented second phase with volume fraction of 0.1% and 0.2% respectively. The addition of Zr also significantly inhibited the coarsening of grains at high temperatures, correspondingly which was associated with the pinning of grain boundaries by Laves phase particles.