Control of nucleation sites is an important goal in materials growth: nuclei in regular arrays may show emergent photonic or electronic behavior, and the nucleation density influences parameters such as surface roughness, stress, and defects such as grain boundaries once the nuclei coalesce into thin films. Tailoring substrate properties to control nucleation is therefore a powerful tool for designing functional thin films and nanomaterials. Here, we examine nucleation control for metals deposited on two-dimensional (2D) materials, focusing on how the condition of the surface determines the nucleation parameters and the resulting structure. Through quantification of faceted, epitaxial Au island nucleation on graphene, we show that ultra-low nucleation densities with nuclei several micrometers apart can be achieved by changing the nature of the support beneath the 2D material to create suspended 2D membranes and eliminating extraneous nucleation sites. Our data highlight the extreme sensitivity of metal nucleation and diffusion on graphene to extrinsic factors and suggest new avenues for applications where long diffusion distances of metals on graphene are required, such as self-assembly of epitaxial nanoparticle arrays or patterning of metals using areas of suspended graphene with low density of nucleation sites.