We report on the growth of palladium nanoparticles on the basal plane of as-cleaved highly oriented pyrolytic graphite (HOPG) samples, and on CO2 ion sputtered nanostructured HOPG surfaces. The morphology of Pd nanostructures grown at room temperature is investigated by scanning tunneling microscopy (STM). The STM observations indicate that the morphology of the Pd films is strongly dependent on the HOPG surface. Stabilized Pd particles only form on the sputtered surface, while ramified Pd particles decorate the clean HOPG terraces. The prestructuring of HOPG surface leads to a selective location of particles at the rim of the nanopits generated by the CO2 ion sputtering and annealing of the surface. The correlation between size, form, density, spatial distribution of the Pd nanoparticles and the quantity of metal added on surface is discussed. We also describe trench channeling of graphite or graphene basal planes by means of Pd nanoparticles in an ambient environment. Copyright (c) 2014 John Wiley & Sons, Ltd.