The present study investigated the use of a laser-beam, in order to carburize the surface of DIN 15CrNi6 low-alloy, case-hardening steel. The surface of the material was coated with graphite prior to laser irradiation. Two different kinds of coatings were used: (i) a dilute commercial graphite spray and (ii) a slurry of graphite powder in ethanol. A CO2 laser-beam was used as the heat source, in order to activate the introduction of carbon in the steel surface. Carburizing was achieved by two distinct mechanisms: (a) surface alloying mechanism, which incorporates melting of the substrate and dissolution of the graphite in the liquid phase and (b) solid-state diffusion mechanism, which incorporates austenitization of the substrate and carbon diffusion in austenite. A variety of microstructures and microhardness profiles were produced, depending mainly on the type of graphite coating used, as well as on processing parameters. In general, the carburized layer was accompanied by a heat-affected zone, which was also significantly hardened, mainly due to secondary hardening. Cracking and porosity was observed in some specimens carburized by the surface alloying mechanism, as a result of carbon enrichment and high solidification rates. Finally, an effort was made to investigate the possibility for solid-state diffusion of carbon in austenite, under the short heating times imposed by laser treatment, with the use of computational kinetics simulation.