STM studies reveal that irregular non-equilibrium two-dimensional Al islands form during deposition of Al on NiAl(110) at 300 K. These structures reflect the multiple adsorption sites and diffusion paths available for Al adatoms on the binary alloy surface, as well as the details of inhibited edge diffusion and detachment-attachment kinetics of Al adatoms for numerous distinct step edge configurations. We attempt to capture these features by multi-site lattice-gas modeling incorporating DFT energetics for adatoms both at adsorption sites and transition states. This formulation enables description and elucidation of the observed island growth shapes.