We discuss the algebro-geometric initial value problem for the Toda hierarchy with complex-valued initial data and prove unique solvability globally in time for a set of initial (Dirichlet divisor) data of full measure. To this effect we develop a new algorithm for constructing stationary complex-valued algebro-geometric solutions of the Toda hierarchy, which is of independent interest as it solves the inverse algebro-geometric spectral problem for generally non-self-adjoint Jacobi operators, starting from a suitably chosen set of initial divisors of full measure. Combined with an appropriate first-order system of differential equations with respect to time (a substitute for the well-known Dubrovin equations), this yields the construction of global algebro-geometric solutions of the time-dependent Toda hierarchy. The inherent non-self-adjointness of the underlying Lax (i.e., Jacobi) operator associated with complex-valued coefficients for the Toda hierarchy poses a variety of difficulties that, to the best of our knowledge, are successfully overcome here for the first time. Our approach is not confined to the Toda hierarchy but applies generally to 1+1-dimensional completely integrable (discrete and continuous) soliton equations.