Two-dimensional (2D) graphene has been widely used as an ideal substrate for many functional materials. It is crucial to understand and control the growth of metal nanocrystals on the graphene surface. Herein we report a novel phenomenon that pre-synthesized palladium nanoparticles are spontaneously transformed into palladium nanostrings (Pd NSs) with nanoscale grain boundaries induced by the reduction of a graphene oxide substrate. A systematic study has been performed to explore the formation mechanism of Pd NSs, where the surface chemistry of 2D graphene is found to be the key factor. More importantly, these Pd NSs exhibit significantly enhanced stability and are among the most active catalysts for formic acid oxidation. Density-functional theory investigation further unravels that the formation of grain boundaries weakens the adsorption of formate and facilitates its subsequent oxidation.