There has been recent interest in expanding the fundamental understanding of catalytic behavior in oxygen-rich conditions on transition metal surfaces. Dramatic improvements in fuel efficiency could be realized if we could operate internal combustion engines in fuel-lean, oxygen-rich conditions, but this would require new catalysts capable of handling the NOx emissions. One issue is the transition of oxygen phases on the metal surfaces from chemisorbed oxygen to surface and bulk oxides, since these phases can have dramatically different reactivity. We have performed density functional theory (DFT) calculations of the oxidation of Pt(111) and Pd(111) surfaces. We have examined the energetic and kinetics of possible mechanisms (subsurface O and metal-O exchange) involved in the initial transition from the chemisorbed surface oxygen phase to the 2D oxide phases. While the subsurface O becomes more stable than surface chemisorbed O at coverages around 3/4 ML, the energy barriers for O to diffuse into the subsurface are very large (> 2 eV). We will report on our efforts to examine alternative mechanisms for O incorporation into the subsurface. Our initial results will serve as a base for future DFT calculations that will examine more complex mechanisms for oxide formation on transition metal surfaces.