Although the changes in melting behaviour on the nanoscale have long attracted the interest of researchers, the mechanism by which nanoparticles melt remains an open problem. We report the direct observation, at atomic resolution, of surface melting in individual size-selected Au clusters (2-5 nm diameter) supported on carbon films, using an in situ heating stage in the aberration corrected scanning transmission electron microscope. At elevated temperatures the Au nanoparticles are found to form a solid core-liquid shell structure. The cluster surface melting temperatures, show evidence of size-dependent melting point suppression. The cluster core melting temperatures are significantly greater than predicted by existing models of free clusters. To explore the effect of the interaction between the clusters and the carbon substrate, we employ a very large-scale ab initio simulation approach to investigate the influence of the support. Theoretical results for surface and core melting points are in good agreement with experiment.