The structural phases of Al(x)Na(1-x) surface alloys have been investigated theoretically and experimentally. We describe the system using a lattice-gas Hamiltonian, determined from density functional theory, together with Monte Carlo (MC) calculations. The obtained phase diagram reproduces the experiment on a quantitative level. From calculation of the (configurational) density of states by the recently introduced Wang-Landau MC algorithm, we derive thermodynamic quantities, such as the free energy and entropy, which are not directly accessible from conventional MC simulations. We accurately reproduce the stoichiometry, as well as the temperature at which an order-disorder phase transition occurs, and demonstrate the crucial role, and magnitude, of the configurational entropy.