Although Electrical Discharge Machining (EDM) is essentially a material removal process, it has been possible to use this technique for surface alloying of the work materials. Traces of additive powders in the dielectric medium have been found in the machined surface. Conductive powders in the dielectric affect the surface finish and micro-hardness. Experimental investigations were carried out for improving the surface properties of Oil-Hardening Non-Shrinkable die steel by graphite tool electrode and by graphite powder mixed in the dielectric. Results show increase in the percentage of carbon in the machined surface from 0.82% to 1.16% by graphite electrode and from 0.82% to 4.11% by graphite powder. SEM micrograph shows smooth surfaces devoid of any craters and nodules of free graphite. Increase in micro-hardness of the machined surfaces is 12.6% and 22.5% respectively. It can be concluded that it is possible to deposit carbon by this method of machining.