We present a model for the oxidation of titanium combining nonequilibrium statistical mechanics and density functional theory (DFT). Using this model, we found that oxygen is more strongly bound as an interstitial in Ti metal than in the oxide TiO2, the energy difference being similar to 1.6 eV. Therefore, a binary phase structure TiO2/Ti, such as the commonly observed oxide scale that protects titanium alloy against corrosion, is thermodynamically unstable. Likewise, various DFT functionals all showed that several TiO2-x compounds have lower energies than the weighted average energy of Ti and TiO2. Thus, the scale is a nonequilibrium structure for which diffusion is the controlling process. We found that the barrier for O-vacancy migration in TiO2 is E-rutile = 0.9 eV, much lower than the interface migration barriers (1.0-1.9 eV). We introduce a particle-based diffusion model that captures this feature and explains the long-lived nature of the observed thin oxide layer.