The work aims to study ball-milling preparation technology of nanostructured Fe40Al alloy powder for cold spraying use and its cold spraying deposition behavior on different substrates. Fe and Al powder was mixed according to Fe-40Al (at.%) and milled in a planetary ball mill to prepare nanostructured Fe40Al alloy powder. Single Fe40Al alloy powder particle was deposited on the surfaces of four substrates of different harness (stainless steel, low carbon steel, pure copper and Tin) by cold spraying. Structural evolution of the Fe40Al alloy powder during ball milling, and its collision deformation behavior and deposition characters on different substrates were analyzed with X-ray diffractometer (XRD) and scanning electron microscope (SEM). Al atom diffused into Fe lattice and finally formed nanostructured Fe(Al) solid solution as the ball milling time extended. After 36 hours of milling, grain size and average particle size of the Fe40Al alloy powder were approximately 35 nm and 20 μm, respectively, and the powder exhibited refined platelike microstructure. When depositing on stainless steel and low carbon steel substrates of relatively high hardness, nanostructured the Fe40Al alloy powder was subject to intensive plastic deformation while the substrate was subject to little deformation. The deposition effect was not good due to relatively poor bonding condition between the particle and substrate. When depositing on Cu substrate of relatively lower microhardness and good plasticity, both the Fe40Al alloy powder and substrate were subject to intensive plastic deformation and deposition effect was the best due to favorable bonding condition between the particle and substrate. When depositing on Sn substrate of the lowest microhardness, the substrate was subject to intensive plastic deformation and even partial melting in local impacting area, deposition effect was the poorest due to weak bond condition between the intact particle and substrate. Nanostructured Fe40Al alloy powder as feedstock of cold spraying process can be fabricated by ball milled process. The grain size of Fe40Al alloy powder decreases while microhardness increases as the ball milling extends. Substrate type has significant effect on the deposition behavior of Fe40Al alloy powder during cold spraying. The Fe40Al alloy powder exhibits relatively poor deposition effect when substrate microhardness is too high or too low. The optimal deposition effect can be obtained since intensive plastic deformation of both the substrate and powder particle contributes to interface bonding between the particle and substrate.