The formation of nanocrystalline structure in steels by ball milling, shot peening and drilling were studied. In ball milling and shot peening, nanocrystalline layers form with sharp boundaries from deformed structure regions. Nanocrystalline layer showed extremely high hardness. By annealing, nanocrystalline layer showed substantially slow grain growth without recrystallization. The temperature of the specimen during deformation is low and deformation is done in ferrite state. In drilling, several μm thick nanocrystalline layers form at the top surface of a drill hole. Nanocrystalline layers showed high hardness and good thermal stability. The fresh martensite and retained austenite near a drill hole indicate that the temperature reached above Ac3 and nanocrystalline layers are produced in austenite condition. It is recognized that nanocrystalline layers produced in the processes studied in the present investigation has similar characteristics irrespective of the temperature it produced. It is proposed that deformation with a large strain gradient is an important condition to produce nanocrystalline structure.