In the present study, a nanostructured FeAl coating was prepared by cold spraying of ball milled powder. Annealing treatment was applied to the coating to investigate its effect on the phase structure, grain size and microhardness of the cold-sprayed nanostructured FeAl coating. The results showed that the FeAl phase was kept unchangeable when the coating annealed at the temperature above 500°C. Annealing temperature significantly influenced the microstructure and microhardness of cold-sprayed FeAl coating. With raising annealing temperature, the lamellar structure in the as-sprayed coating disappeared and a dense coating microstructure with fully bonding of deposited particles at their interfaces was achieved after annealing at 950°C. Nanograin growth of the FeAl phase occurred at an annealing temperature higher than 800°C. The microhardness of cold-sprayed FeAl coating remained about 400 Hv0.1 at the annealing temperature below 800°C and decreased to 300 Hv0.1 at 1100°C.