In the cold spraying process, particle velocity is commonly regarded as the key factor that influences the deposition efficiency and properties of the coating. The present paper reports on a study in which the velocity of in-flight particles was measured using a DPV-2000 system. The influences of He and N2 gas pressure and temperature and particle morphology on the particle velocity and deposition efficiency of the coating using stainless steel 316L powders were studied. The microstructure of the coating was examined using optical microscopy. The critical velocity of stainless steel 316L powders was estimated according to the particle velocity distribution and deposition efficiency of the coating. The experiment results suggested that the gas pressure has a more significant influence on the particle velocity and deposition efficiency of the coating than the gas temperature. The particle morphology also has significant influence on the particle velocity. The critical velocity of stainless steel 316L powders was in the range of 630 to 680 m/s, and it decreased slightly with the gas temperature.