First-principles calculations of high-temperature spin dynamics in solids in the context of nuclear magnetic resonance (NMR) is a long-standing problem, whose conclusive solution can significantly advance the applications of NMR as a diagnostic tool for material properties. In this work, we propose a new hybrid quantum-classical method for computing NMR free induction decay(FID) for spin $1/2$ lattices. The method is based on the simulations of a finite cluster of spins $1/2$ coupled to an environment of interacting classical spins via a correlation-preserving scheme. Such simulations are shown to lead to accurate FID predictions for one-, two- and three-dimensional lattices with a broad variety of interactions. The accuracy of these predictions can be efficiently estimated by varying the size of quantum clusters used in the simulations.