Techniques to produce nanostructured materials are severe plastic deformation (SPD) and surface severe plastic deformation (SSPD). This paper reports our study on severe plastic deformation that applied on samples surfaces with sandblasting by hard particles of silica and then annealing. The samples were made of nitriding steel PO733 (DIN: 1.8509). The grain size of the nanocrystalline surface layer was in the range of 20 nm, determined by using scanning electron microscopy (SEM) and X-ray diffraction (XRD) analysis. Mechanical behavior of nanocrystalline surface was investigated using micro hardness test. The result show grain size decreases to nanometer scale (even 15 nm), by increase time of sandblasting, but this decreasing is not linear. Thickness of nanocrystalline surface is independent by time of sandblasting and its stable. It was demonstrated that the mechanical behavior of samples surface was markedly improved when its grain size was reduced to nanoscale. The nanocrystalline surface caused by the sandblasting and annealing treatment exhibited considerably higher hardness.