Ni-based coatings IN625® and Ni20%Cr were cold sprayed on a low-alloy steel (AISI 4130) substrate, using Helium as the process gas. Dense coatings up to 3-mm thickness were deposited, having a hardness of 500-550 HV. The coatings showed a hardness maximum, with heat treatment, before dropping to a lower value. The coating microstructure revealed two distinct types of regions, comprising grains with a high dislocation density and elongated shear bands having twins. Heat treatment led to 30-50 nm grains in the IN625 coating, and >1-2 μm grains for NiCr. Both coatings showed a compressive residual stress in the as-sprayed condition, which relaxed to a zero residual stress, at 650 °C. The NiCr coatings showed a much higher compressibility, as compared to IN625. The IN625 coatings induced a much larger deformation on the 4130 steel. Overall, while both types of Ni-based alloy coatings showed similarities in terms of hardness and microstructure, they revealed distinct differences in their deformability, thermal stability, and substrate deformation, indicating a different behavior between a binary solid solution (NiCr) as compared to a multielement solid solution (IN625), as elucidated via a detailed characterization of these coatings.