We present temperature-dependent X-ray reflectivity measurements of liquid Hg alloyed with 0.06-0.20 atom % Au. At low Au concentrations, we find temperature-dependent surface-induced layering similar to that observed in pure HE, except that the presence of Au reduces the layering amplitude. Upon approaching the solubility limit of Au in Hg. a new surface phase forms which is 1-2 atomic diameters thick and has a density of about half that of bulk Hg. We present a surface phase diagram, summarizing the evolution of this unexpected surface structure upon varying composition and temperature, Such surface modifications may account for the variations observed in catalytic and electrochemical reactions at liquid metal surfaces upon alloying.