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 ot=3$. Moreover the warp factor of AdS$_3$ backgrounds is constant, the geometry is a product $AdS_3times 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-Kahler structure, respectively. We also demonstrate a new Lichnerowicz type theorem in the presence of $alpha$ corrections.