© 2018 American Chemical Society. Enhancing the spin-orbit interaction in graphene, via proximity effects with topological insulators, could create a novel 2D system that combines nontrivial spin textures with high electron mobility. To engineer practical spintronics applications with such graphene/topological insulator (Gr/TI) heterostructures, an understanding of the hybrid spin-dependent properties is essential. However, to date, despite the large number of experimental studies on Gr/TI heterostructures reporting a great variety of remarkable (spin) transport phenomena, little is known about the true nature of the spin texture of the interface states as well as their role on the measured properties. Here, we use ab initio simulations and tight-binding models to determine the precise spin texture of electronic states in graphene interfaced with a Bi2Se3 topological insulator. Our calculations predict the emergence of a giant spin lifetime anisotropy in the graphene layer, which should be a measurable hallmark of spin transport in Gr/TI heterostructures and suggest novel types of spin devices.