Electrodeposition of Au onto HOPG and CVD graphene electrodes has been undertaken with the aim of determining parameters to control growth and obtain small particles with a narrow size distribution. This was achieved using a double potential step profile, where a short, high overpotential nucleation pulse creates all the nuclei at the beginning of the experiment, followed by a growth potential, chosen so that the nuclei grow but no new nuclei form. Such control means that electrodeposition is a promising alternative to the chemical and evaporation methods that are routinely used to modify these substrates.