In this letter we show that it is possible to guide the formation of a novel non-close-packed xenon structure on a stepped nickel surface using an intentionally atomically patterned substrate. By first defining the symmetry and desired dimensions of the underlying superlattice, we successfully template the targeted rare-gas overlayer. Such templating effects, in which the corrugation and structure of the interface can be tuned by prior adsorption of an adsorbate, should be a general route to the formation of new self-organizing interfacial nanoscale structures.