Degradation of the mechanical properties of α-titanium, which is used to manufacture parts of jet engines, due to high-temperature oxidation is detrimental for the engine components. Therefore, to overcome this problem there are ongoing endeavors to develop novel oxidation-resistant titanium alloys and improve the properties of the existing ones. In an effort to understand the effect of alloying on oxidation of the α-Ti(0001) surface and to identify descriptors for rational design of oxidation-resistant alloys, in this work, using density functional theory-based calculations, we studied oxygen sorption and surface to subsurface diffusion on pure and alloyed α-Ti(0001) surfaces. Zr, Hf, Nb, and Mo from the d block and Al, Ga, Si, and Ge from the p block were used as alloying elements. We find that the alloying elements prefer to segregate on the surface compared to the subsurface layers. Our calculations show that the diffusion barrier correlates with the difference in the electronegativity between the alloying element and Ti. Elements which are more electropositive than Ti are found to hinder the oxygen dissolution in Ti and vice versa. We propose that the electronegativity difference can act as a good descriptor for choosing alloying elements. Our results are in reasonably good agreement with experimental reports on the growth of oxide layers on these alloyed Ti surfaces.