Control over the two-dimensional electron gas (2DEG) in AlGaN/GaN heterostructures is crucial for their practical applications in current semiconducting devices. However, the oxide surface structures inducing 2DEG are still ambiguous because oxide-stoichiometry (OS) matching structures possess occupied surface donor states at 1.0–1.8 eV below the conduction band minimum of bulk but are usually not available in energy than electron counting (EC) rule structures. In this work, a global optimization algorithm was introduced to explore the possible oxidation structures on GaN (0001) and AlN (0001) surfaces; the method was demonstrated to be available due to the fact that the reported oxidized structures were reproduced at each stoichiometry. Interestingly, the two similar oxide structures with close energy were found in each oxide-bilayer, which can be used to clarify the experimental observations of disordered surface oxide layers below 550 °C. Additionally, new stable oxidation structures with low surface energy were proposed. Interestingly, the new OS matching structures are proposed with remarkably lower energy than EC rule structures under cation-rich and oxygen-poor conditions, which is caused by the large formation enthalpy of Al2O3 and Ga2O3. Further electronic structure calculations demonstrate that the new OS structures possess highest occupied states above the half of the gap and are the origin of 2DEG in AlGaN/GaN heterostructures.