Scanning tunneling microscopy studies reveal that two-dimensional nanoscale Ni islands formed by deposition of Ni on NiAl(110) between 200–400 K exhibit far-from-equilibrium growth shapes which change systematically with temperature. Island structure reflects the two types of adsorption sites available for Ni adatoms, and island shapes are controlled by the details of adatom diffusion along island edges accounting for numerous local configurations. The temperature dependence of the island shapes is captured and elucidated by kinetic Monte Carlo simulation of a realistic atomistic-level multisite lattice-gas model incorporating precise diffusion barriers. These barriers are obtained by utilizing density functional theory to probe energetics not just at adsorption sites but also at transition states for diffusion. This success demonstrates a capability for predictive atomistic-level modeling of nanocluster formation and shape selection in systems that have a high level of energetic and kinetic complexity.