The dissociation of carbonaceous molecules on the surface of a nano-sized Ni crystal induces deep morphological changes way below the melting temperature, as imaged by Field Ion Microscopy. In this Letter, classical Molecular Dynamics (MD) was used to demonstrate that carbon adsorption triggers Ni surface diffusion. More precisely, single adsorbed carbon atoms, preferentially bound to 5-fold surface sites, enhance thermally activated Ni diffusion. A mechanism is identified by which adsorbed carbon promotes the rupture of surface Ni atoms from their lattice position. This leads to a destabilization of edges between facets of the Ni crystal. (C) 2010 Elsevier B.V. All rights reserved.