We study the properties of M and F theory compactifications to three and fo
ur dimensions with background fluxes. We provide a simple construction of s
upersymmetric vacua, including some with orientifold descriptions. These va
cua, which have warp factors, typically have fewer moduli than conventional
Calabi-Yau compactifications. The mechanism for anomaly cancellation in th
e orientifold models involves background RR and NS fluxes. We consider in d
etail an orientifold of K3 x T-2 with background fluxes. After a combinatio
n of T and S-dualities, this type IIB orientifold is mapped to a compactifi
cation of the SO(32) heterotic string on a non-Kahler space with torsion.