We present a combined experimental and theoretical investigation of the magnetic behavior of ultra-thin Cr films grown on oxygen-passivated Fe(001)-p(1×1)O substrates. In all cases, oxygen floats on the metal/vacuum interface, where a monolayer-range oxide with peculiar electronic and structural characteristics is formed. Significant differences with previous experimental realizations of the Cr/Fe(001) heterostructure are thus introduced by the presence of oxygen. However, we show here that the magnetic behavior of our system is characterized by the same AF stacking at the Cr-Fe interface and by a layer-wise AF order in the Cr layer. In addition, we are able to circumvent the issue of chemical mixing at the Cr-Fe interface, characteristic of standard preparations.