  We study heterotic backgrounds with non-trivial $H$-flux and non-vanishing
expectation values of fermionic bilinears, often referred to as gaugino
condensates. The gaugini appear in the low energy action via the
gauge-invariant three-form bilinear $\Sigma_{MNP}={\rm
tr}\:\bar\chi\Gamma_{MNP}\chi$. For Calabi-Yau compactifications to four
dimensions, the gaugino condensate corresponds to an internal three-form
$\Sigma_{mnp}$ that must be a singlet of the holonomy group. This condition
does not hold anymore when an internal $H$-flux is turned on and ${\cal
O}(\alpha')$ effects are included. In this paper we study flux
compactifications to three and four-dimensions on $G$-structure manifolds. We
derive the generic conditions for supersymmetric solutions. We use
integrability conditions and Lichnerowicz type arguments to derive a set of
constraints whose solution, together with supersymmetry, is sufficient for
finding backgrounds with gaugino condensate.
