Kane and Mele predicted that in the presence of spin-orbit interaction graphene realizes the quantum spin Hall state [Phys. Rev. Lett. 95, 226801 (2005)]. However, exceptionally weak intrinsic spin-orbit splitting in graphene (approximate to 10(-5) eV) inhibits experimental observation of this topological insulating phase. To circumvent this problem, we propose an approach towards controlling spin-orbit interactions in graphene by means of covalent functionalization of graphene edges with functional groups containing heavy elements. Proof-of-concept first-principles calculations show that very strong spin-orbit coupling can be induced in realistic models of narrow graphene nanoribbons with tellurium-terminated edges. We demonstrate that electronic bands with strong Rashba splitting as well as the quantum spin Hall state spanning broad energy ranges can be realized in such systems. Our work thus helps pave the way towards engineering topological electronic phases in nanostructures based on graphene and other materials by means of locally introduced spin-orbit interactions.