New industries have a growing need for high temperature lubricant coatings to reduce friction and wear. A promising nanostructured Ni-based self-lubricating wear-resistant coating was deposited via cold spray of a pre-synthesized nano-crystalline In625-Cr2O3-Ag powder. A nanostructured feedstock powder with a composition of 70% In625, 20% Cr2O3 and 10% Ag (mass percentages) was first synthesized by the ball milling approach, then the corresponding coating was deposited by the cold spraying process. The tribological properties of the as-sprayed coating were tested by a high temperature tribometer at 20,400 and 1000 °C under dry sliding conditions. Meanwhile, the thermal stability of the cold sprayed nanostructured composite coating was investigated by a heat treatment at 1000 °C. The experimental results indicate that the cold sprayed nanostructured coating produces low friction coefficient around 0.3 and exhibits excellent wear resistance around the order of 10−5 mm3/(N·m) at all tested temperatures. More importantly, no evident enrichment of silver or serious damage is observed on the surface of the coating after a heat treatment at 1000 °C for 50 h, which indicates that the nanostructured coating exhibits good thermal stability at high temperature. The results of this study suggested that the novel cold sprayed nanostructured Ni-based coating could be valuable for sliding contact components in high temperature tribo-systems.