We investigate four-dimensional Heterotic solitons, defined as a particular class of solutions of the equations of motion of Heterotic supergravity on a four-manifold M or, equivalently, as self-similar points of the renormalization group flow of the NS-NS sector of the Heterotic world-sheet. Heterotic solitons depend on a parameter κ and consist of a Riemannian metric g, a metric connection with skew torsion H on TM and a closed 1-form ϕ on M satisfying a differential system that generalizes the celebrated Hull-Strominger system. In the limit κ → 0, Heterotic solitons reduce to a class of generalized Ricci solitons and can be considered as a higher-order curvature modification of the latter. If the torsion H is equal to the Hodge dual of ϕ, Heterotic solitons consist of either flat tori or Ricci-flat Weyl structures on manifolds of type S1 x S3 as introduced by P. Gauduchon. We prove that the moduli space of such Ricci-flat Weyl structures is isomorphic to the product of R with a certain finite quotient of the Cartan torus of the isometry group of the typical fiber of a natural fibration M → S1. We also consider the associated space of essential infinitesimal deformations, which we prove to be obstructed. More generally, we characterize several families of Heterotic solitons as suspensions of certain three-manifolds with prescribed constant principal Ricci curvatures, amongst which we find hyperbolic manifolds, manifolds covered by Sl(2,R) and E(1,1) or certain Sasakian three-manifolds. These solutions exhibit a topological dependence in the string slope parameter κ and yield, to the best of our knowledge, the first examples of Heterotic compactification backgrounds not locally isomorphic to supersymmetric compactification backgrounds.