Enhanced surface properties could be achieved by coating with nano-materials. Plasma spayed coatings are widely used. However, porosity in the coating deteriorates corrosion resistance. Therefore, epitaxially grown porous free nano-structured coating would be an ideal choice for imparting enhanced surface properties. A nano-crystalline surface with well defined grain size of less than 20 nm could be achieved by surface deformation followed by a low temperature annealing. This paper will discuss the processing steps of creating an optimized nano-crystalline surface layer on Alloy-22, a Ni-Cr-Mo-W alloy. Corrosion resistance of the nano-crystalline surface of Alloy-22 will be compared with that of conventional material. Scanning Kelvin Probe studies are being carried out to investigate the potential gradients across the passive films of nano-crystalline surface. Results of these studies coupled with TEM analyses will help understand the underlying mechanism for improved corrosion resistance of nano-structured surface.