The paper is dedicated to theoretical-experimental research on the formation of micro- and nano-structures on metallic surfaces under conditions of pulsed electric discharge machining (PEDM). In the case of the processing of construction steels with the graphite tool-electrode by applying PEDM in maintenance regime of the „cold” electrode spots, the formation of graphite structures (of the fullerene and single-walled carbon nanotube type) of the nanometric order was detected. Due to the superior mechanical properties, the coatings with micro- and nano-dimensional layers of carbon on the metal base can be applied to the processing of machine building parts in order to increase the wear resistance of the active surfaces.