Natural surfaces are often structured with nanometre-scale domains, yet a framework providing a quantitative understanding of how nanostructure affects interfacial energy, gamma(SL), is lacking. Conventional continuum thermodynamics treats gamma(SL) solely as a function of average composition, ignoring structure. Here we show that, when a surface has domains commensurate in size with solvent molecules, gamma(SL) is determined not only by its average composition but also by a structural component that causes gamma(SL) to deviate from the continuum prediction by a substantial amount, as much as 20% in our system. By contrasting surfaces coated with either molecular- (<2 nm) or larger-scale domains (>5 nm), we find that whereas the latter surfaces have the expected linear dependence of gamma(SL) on surface composition, the former show a markedly different non-monotonic trend. Molecular dynamics simulations show how the organization of the solvent molecules at the interface is controlled by the nanostructured surface, which in turn appreciably modifies gamma(SL).