A formalism for the systematic construction of integrable non-autonomous deformations of soliton hierarchies is presented. The theory is formulated as an initial value problem (IVP) for an associated Frobenius integrability condition on a Lie algebra. It is shown that this IVP has a formal solution, and within the framework of two particular subalgebras of the hereditary Lie algebra, the explicit forms of this formal solution are derived. Finally, this formalism is applied to the Korteveg-de Vries, dispersive water waves and Ablowitz-Kaup-Newell-Segur soliton hierarchies. The zero-curvature representations and Hamiltonian structures of the considered non-autonomous soliton hierarchies are also provided.