Scanning tunneling microscopy reveals that domain walls in ultrathin Fe nanowires are oriented along a certain crystallographic direction, regardless of the orientation of the wires. Monte Carlo simulations on a discrete lattice are in accordance with the experiment if the film relaxation is taken into account. We demonstrate that the wall orientation is determined by the atomic lattice and the resulting strength of an effective exchange interaction. The magnetic anisotropy and the magnetostatic energy play a minor role for the wall orientation in that system.