Nano-structured materials often possess special properties that materials with identical compositions but ordinary grain size do not have. This paper reports our work on the surface nano-crystallisation and nano-structured alloy and composite coatings. A number of processing methods including magnetron sputtering, thermal spray and pulse electro-spark deposition have been used to produce surface nano-crystalline structure. The compositions and microstructures can be well controlled by using different targets or electrodes, nano-structured composites and adjusting processing parameters. Surface nano-structured coatings can provide special chemical, mechanical and electronic properties such as high temperature corrosion and corrosive wear resistance. It has potential applications such as turbine blades, engine parts for petrochemical, aerospace and electronic device industries. This paper is focused on the study of the interrelations between processing, microstructure and properties. Physical models have been established to explain the effects of nano-crystalline structure on the properties.