Properties of AlN/GaN surfaces are important for realizing the tunability of devices, as the presence of surface states contributes to Fermi level pinning. This pinning can influence the performance of high electron mobility transistors and is also important for passivation of the surface when developing high-power electronic devices. It is widely understood that both AlN and GaN surfaces oxidize. Since there are many possible reconstructions for each surface, it is a challenge to identify the relevant surface reconstructions in advance of a detailed simulation. Because of this, different approaches are often employed to down select initial structures to reduce the computational load. These approaches usually rely on either electron counting rules or oxide stoichiometry, as both of these models tend to lead to structures that are energetically favorable. Here we explore models from these approaches but also explore a reconstruction of the (0001) surface directly observed using scanning transmission electron microscopy with predictive density functional theory simulations. Two compositions of the observed surface reconstruction—one which obeys oxide stoichiometry and one which is cation deficient and obeys electron counting—are compared to reconstructions from the previous work. Furthermore, surface states are directly calculated using hybrid exchange-correlation functionals that correct for the underestimation of the bandgaps in AlN and GaN and improve the predicted positions of surface states within the gap. It is found that cation deficiency in the observed reconstruction yields surface states consistent with the experiment. Based on all of these results, we provide insight into the observed properties of oxidized AlGaN surfaces.