Van der Waals heterostructures have become a paradigm for designing new materials and devices in which specific functionalities can be tailored by combining the properties of the individual 2D layers. A single layer of transition-metal dichalcogenide (TMD) is an excellent complement to graphene (Gr) because the high quality of charge and spin transport in Gr is enriched with the large spin–orbit coupling of the TMD via the proximity effect. The controllable spin-valley coupling makes these heterostructures particularly attractive for spintronic and opto-valleytronic applications. In this work, we study spin precession in a monolayer MoSe2/Gr heterostructure and observe an unconventional, dramatic modulation of the spin signal, showing 1 order of magnitude longer lifetime of out-of-plane spins compared to that of in-plane spins (τ⊥ ≈ 40 ps and τ∥ ≈ 3.5 ps). This demonstration of a large spin lifetime anisotropy in TMD/Gr heterostructures, is a direct evidence of induced spin-valley coupling in Gr and provides an accessible route for manipulation of spin dynamics in Gr, interfaced with TMDs.