A two dimensional crystalline layer is found at the surface of the liquid eutectic Au$_{82}$Si$_{18}$ alloy above its melting point $T_M=359 ^{circ}$C. Underlying this crystalline layer we find a layered structure, 6-7 atomic layers thick. This surface layer undergoes a first-order solid-solid phase transition occurring at $371 ^{circ}$C. The crystalline phase observed for T$>$371 $^{circ}$C is stable up to at least 430 $^{circ}$C. Grazing Incidence X-ray Diffraction data at T$>$371 $^{circ}$C imply lateral order comprising two coexisting phases of different oblique unit cells, in stark contrast with the single phase with a rectangular unit cell found for low-temperature crystalline phase $359 ^{circ}$C$<T<371 ^{circ}$C.