It is shown that the spin-polarization direction of the reflected electrons on Fe(001) strongly changes with minute amounts of MgO. Our ab initio electronic band structure and spin-dependent electron reflection calculations reveal that the MgO-induced out-of-plane-relaxation of the Fe surface is responsible for this behavior. Our study points toward the subtle feature that the major change of the spin-dependent electron reflection properties of the Fe(001) surface is already caused by the very first MgO coverage.