Corundum (α-Al2O3) is the thermodynamically stable form of aluminum oxide and used in many fields of technology. Nevertheless, the structures of its surfaces have not been determined yet. Our high-quality ncAFM images of the Al2O3(0001)-(√31×√31)R±9∘ reconstruction, which forms after high-temperature annealing, rule out the aluminum termination proposed previously [1,2]. The surface is very similar to ultrathin alumina films, which have well-established structural models [3,4]. To determine the structure of the subsurface layers not directly imaged by ncAFM, we employed density functional theory calculations and machine-learned force fields to search the large configuration space, resulting in a lowest-energy structure that fits the experiment. DFT calculations also show that the standard model for the unreconstructed Al2O3(0001)-(1× 1) surface cannot be thermodynamically stable at any conditions. We discuss reasons for the high stability of the reconstruction.