Surface alloying is a powerful way of varying physical and chemical properties of metals, for a number of applications from catalysis to nuclear and green technologies. Surfaces offer many degrees of freedom, giving rise to new phases that do not have a bulk counterpart. However, the atomic characterization of distinct surface compounds is a major task, which demands powerful experimental and theoretical tools. Here we illustrate the process for the case of a GdAu2 surface phase of extraordinary crystallinity. The combined use of surface-sensitive techniques and state-of-the-art ab initio calculations disentangles its atomic and electronic properties. In particular, the stacking of the surface layers allows for gadolinium's natural ferromagnetic state, at variance with the bulk phase, where frustration leads to antiferromagnetic interlayer coupling.