We determine the interface energy and the work of separation of the Fe/Cr2O3 interface using first-principles density functional theory. Starting from different structures, we put forward a realistic interface model that is suitable to study the complex metal-oxide interaction. This model has the lowest formation energy and corresponds to an interface between Fe and oxygen terminated Cr2O3. The work of separation is calculated to be smaller than the intrinsic adhesion energy of pure Fe or Cr2O3, suggesting that stainless steel surfaces should preferentially break along the metal-oxide interface. The relative stabilities and magnetic interactions of the different interfaces are discussed. Next we introduce Cr atoms into the Fe matrix at different positions relative to the interface. We find that metallic Cr segregates very strongly to the (FeCr)/Cr2O3 interface, and increases the separation energy of the interface, making the adhesion of the oxide scale mechanically more stable. The Cr segregation is explained by the enthalpy of formation.