  We show that six-dimensional backgrounds that are T^2 bundle over a
Calabi-Yau two-fold base are consistent smooth solutions of heterotic flux
compactifications. We emphasize the importance of the anomaly cancellation
condition which can only be satisfied if the base is K3 while a T^4 base is
excluded. The conditions imposed by anomaly cancellation for the T^2 bundle
structure, the dilaton field, and the holomorphic stable bundles are analyzed
and the solutions determined. Applying duality, we check the consistency of the
anomaly cancellation constraints with those for flux backgrounds of M-theory on
eight-manifolds.
