The early stages of the oxidation of stainless steel is studied using first principles density functional theory calculations. A Monte Carlo approach was used to efficiently identify the most probable low energy structures in the high-dimensional configuration space. The composition, structure, and oxidation states of the atoms in the oxide layers were analyzed by atomic density profiles, nearest neighbor distribution, and Bader charge analysis. The results suggest that the passivation of steel by chromium is largely due to its high preference for the Cr3+ oxidation state with 6 oxygen neighbors.  In contrast, iron is more susceptible to oxygen penetration because of its variable oxidation state between Fe2+ and Fe3+, and a range nearest oxygen neighbor numbers.