Dirac materials such as graphene and topological insulators (TIs) are known to have unique electronic and spintronic properties. We combine graphene with TIs in van der Waals heterostructures to demonstrate the emergence of a strong proximity-induced spin-orbit coupling in graphene. By performing spin transport and precession measurements supported by ab initio simulations, we discover a strong tunability and suppression of the spin signal and spin lifetime due to the hybridization of graphene and TI electronic bands. The enhanced spin-orbit coupling strength is estimated to be nearly an order of magnitude higher than in pristine graphene. These findings in graphene-TI heterostructures could open interesting opportunities for exploring exotic physical phenomena and new device functionalities governed by topological proximity effects.