The formation of a new type of ordered 2D Ni3Al overlayer by low-temperature codeposition on NiAl(110) is demonstrated by kinetic Monte Carlo simulation of a multisite atomistic lattice-gas model with a precise treatment of surface diffusion kinetics. Simultaneous codeposition with 3:1 Ni:Al yields poor ordering at 300 K but well-ordered structures by ~500 K. Sequential codeposition of Ni then Al yields unmixed core-ring nanostructures at 300 K but strong intermixing and ordering by ~500 K.