We report on fundamental aspects of spin dynamics in heterostructures of graphene and transition metal dichalcogenides (TMDCs). By using realistic models derived from first principles we compute the spin lifetime anisotropy, defined as the ratio of lifetimes for spins pointing out of the graphene plane to those pointing in the plane. We find that the anisotropy can reach values of tens to hundreds, which is unprecedented for typical 2D systems with spin-orbit coupling and indicates a qualitatively new regime of spin relaxation. This behavior is mediated by spin-valley locking, which is strongly imprinted onto graphene by TMDCs. Our results indicate that this giant spin lifetime anisotropy can serve as an experimental signature of materials with strong spin-valley locking, including graphene-TMDC hetero-structures and TMDCs themselves. Additionally, materials with giant spin lifetime anisotropy can provide an exciting platform for manipulating the valley and spin degrees of freedom, and for designing novel spintronic devices.