On the basis of the density-functional theory, cluster models of the adsorption of oxygen atoms on aluminum oxide are constructed and the corresponding potential-energy surface is calculated. Quantum-mechanical calculations showed that it is necessary to take into account the angular dependence of the potential-energy surface and the relaxation of the surface monolayers. Using this surface in molecular dynamics calculations made it possible to obtain the probabilities of the heterogeneous recombination of oxygen atoms on the α-Al2O3 surface, which are in good agreement with experimental data. The calculations performed substantially decrease the amount of experimental investigations necessary reliably to describe the heterogeneous catalysis on promising reusable heat shield coatings for analyzing heat transfer during spacecraft entry into the atmosphere.