  Compactifications of the heterotic string with NS flux normally require non
Calabi-Yau internal spaces which are complex but no longer K\"ahler. We point
out that this conclusion rests on the assumption of a maximally symmetric
four-dimensional space-time and can be avoided if this assumption is relaxed.
Specifically, it is shown that an internal Calabi-Yau manifold is consistent
with the presence of NS flux provided four-dimensional space-time is taken to
be a domain wall. These Calabi-Yau domain wall solutions can still be
associated with a covariant four-dimensional N=1 supergravity. In this
four-dimensional context, the domain wall arises as the "simplest" solution to
the effective supergravity due to the presence of a flux potential with a
runaway direction. Our main message is that NS flux is a legitimate ingredient
for moduli stabilization in heterotic Calabi-Yau models. Ultimately, the
success of such models depends on the ability to stabilize the runaway
direction and thereby "lift" the domain wall to a maximally supersymmetric
vacuum.
