  We classify the geometries of the most general warped, flux AdS backgrounds
of heterotic supergravity up to two loop order in sigma model perturbation
theory. We show under some mild assumptions that there are no $AdS_n$
backgrounds with $n\not=3$. Moreover the warp factor of AdS$_3$ backgrounds is
constant, the geometry is a product $AdS_3\times M^7$ and such solutions
preserve, 2, 4, 6 and 8 supersymmetries. The geometry of $M^7$ has been
specified in all cases. For 2 supersymmetries, it has been found that $M^7$
admits a suitably restricted $G_2$ structure. For 4 supersymmetries, $M^7$ has
an $SU(3)$ structure and can be described locally as a circle fibration over a
6-dimensional KT manifold. For 6 and 8 supersymmetries, $M^7$ has an $SU(2)$
structure and can be described locally as a $S^3$ fibration over a
4-dimensional manifold which either has an anti-self dual Weyl tensor or a
hyper-K\"ahler structure, respectively. We also demonstrate a new Lichnerowicz
type theorem in the presence of $\alpha'$ corrections.
