Single-crystal palladium nanoparticles (NPs) with controllable morphology were synthesized on the surface of reduced graphene oxide (RGO) by a novel procedure, namely reducing palladium acetylacetonate [Pd(acac)2] with the N-methylpyrrolidone (NMP) solvent in the presence of poly(vinylpyrrolidone) (PVP). The resulting Pd nanocrystals (8 nm in diameter) were uniformly distributed on the RGO. A possible formation mechanism is discussed. The electrocatalytic performance of Pd nanocrystal/RGO catalysts during formic acid oxidation was investigated, which revealed that the cubic Pd/RGO catalyst performed significantly better than the spherical Pd/RGO catalyst. The shape of Pd nanocrystals on the surface of graphene nanosheets can be easily controlled via tuning the synthesis parameters, resulting in tunable catalytic properties. Moreover, this method can be easily extended to fabricate other noble metal nanostructures.