The work aims to study the influence of crystal size, structure and super-cooling on the microhardness of NJ-4 alloy coating and find out the optimum microhardness of the structure and crystal size. Orthogonal experiment was used to carry out laser cladding to the substrate. Then, the influence of structure crystal size and super-cooling degree on hardness of alloy coating was analyzed. From the results, the microhardness of different tissue structures was very different. Dendrite crystal, equiaxed crystal, cellular crystal, equiaxed crystal, dendrite crystal and banded martensite were respectively distributed from the upper surface to the lower surface of cladding layer. When the crystal structure changed in turn, the microhardness firstly increased, then decreased and finally increased again. The microhardness was greatest in the equiaxial crystals at the upper part of the cladding layer. The microhardness was also affected by crystal size and overcooling. The special cooling environment provided by the laser for solidification of molten pool inhibited the precipitation of impurities in solidification process and reduced the production probability of defects to improve the hardness of the cladding layer. The lamellar martensite produced by the laser cladding layer was inlaid between the substrate and the cladding layer and improved the metallurgical bonding strength. Through the measurement, the microhardness of the cladding layer was more than 2.5 times of that in the substrate. The micro- hardness is determined by the structure, crystal size and the degree of supercooling.