Gold nano-clusters were grown on chemically modified graphene by direct sputter deposition. Transmission electron microscopy of the nano-clusters on these electron-transparent substrates reveals an unusual bimodal island size distribution (ISD). A kinetic Monte Carlo model of growth incorporating a size-dependent cluster mobility rule uniquely reproduces the bimodal ISD, providing strong evidence for the mobility of large clusters during surface growth. The cluster mobility exponent of −5/3 is consistent with cluster motion via one-dimensional diffusion of gold atoms around the edges of the nano-clusters.