Surfaces of aluminum alloys are often coated with ultra-thin alumina films which form by self-limited selective oxidation. Although the presence of such films is of paramount importance in various applications, their structural and stability characteristics remain far from being known. In particular, on the NiAl(100) substrate, the observed structure has been tentatively assigned to a distorted θ-alumina polymorph, but the film stoichiometry, the nature of its surface and interface terminations, as well as the mechanisms that stabilize the θ phase remain unknown. Using a combined tight-binding/DFT genetic algorithm approach, we explicitly demonstrate that ultra-thin θ(100)-type films correspond to the structural ground state of alumina supported on the (2 × 1)-NiAl(100) substrate. Thus, experimentally observed θ-alumina films correspond to thermodynamic equilibrium, rather than being the result of kinetic effects involved in the alloy oxidation and film growth. They are favoured over other Al2O3 phases of dehydrated boehmite, pseudo-CaIrO3, γ, or bixbyite structures, which have recently been identified among the most stable free-standing ultra-thin alumina polymorphs. Moreover, our results prove that nonstoichiometry can be easily accommodated by the supported θ(100) film structure via an excess or deficiency of oxygen atoms at the very interface with the metal substrate. Dedicated DFT analysis reveals that the oxide-metal interaction at stoichiometric interfaces depends surprisingly little on the composition of the NiAl surface. Conversely, at oxygen-rich/poor interfaces, the number of additional/missing Al–O bonds is directly responsible for their relative stability. Finally the comparison between the experimental and theoretical electronic characteristics (STM and XPS) of supported θ(100)-type films provides clues on the detailed structure of the experimentally observed films.