In this thesis, we study compactifiations of ten-dimensional heterotic supergravity at O(α'), focusing on the moduli of such compactifications. We begin by studying supersymmetric compactifications to four-dimensional maximally symmetric space, commonly referred to as the Strominger system. The compactifications are of the form M₁₀ = M₄ x X, where M₄ is four-dimensional Minkowski space, and X is a six-dimensional manifold of what we refer to as heterotic SU(3)-structure. We show that this system can be put in terms of a holomorphic operator D on a bundle Q = T* X ⊕ End(TX) ⊕ End(V ) ⊕ TX, defined by a series of extensions. Here V is the E₈ x E₈ gauge-bundle, and TX is the tangent bundle of the compact space X. We proceed to compute the infinitesimal deformation space of this structure, given by TM = H^(0,1)(Q), which constitutes the infinitesimal spectrum of the lower energy four-dimensional theory. In doing so, we find an over counting of moduli by H^(0,1)(End(TX)), which can be reinterpreted as O(α') field redefinitions. In the next part of the thesis, we consider non-maximally symmetric compactifications of the form M₁₀ = M₃ x Y , where M₃ is three-dimensional Minkowski space, and Y is a seven-dimensional non-compact manifold with a G₂-structure. We write X → Y → ℝ, where X is a six dimensional compact space of half- at SU(3)-structure, non-trivially fibered over ℝ. These compactifications are known as domain wall compactifications. By focusing on coset compactifications, we show that the compact space X can be endowed with non-trivial torsion, which can be used in a combination with %α'-effects to stabilise all geometric moduli. The domain wall can further be lifted to a maximally symmetric AdS vacuum by inclusion of non-perturbative effects in a heterotic KKLT scenario. Finally, we consider domain wall compactifications where X is a Calabi-Yau. We show that by considering such compactifications, one can evade the usual no-go theorems for flux in Calabi-Yau compactifications, allowing flux to be used as a tool in such compactifications, even when X is Kähler. The ultimate success of these compactifications depends on the possibility of lifting such vacua to maximally symmetric ones by means of e.g. non-perturbative effects.