Graphene's extremely small intrinsic spin-orbit (SO) interaction makes the realization of many interesting phenomena such as topological/quantum spin Hall states and the spin Hall effect (SHE) practically impossible. Recently, it was predicted that the introduction of adatoms in graphene would enhance the SO interaction by the conversion of sp 2 to sp 3 bonds. However, introducing adatoms and yet keeping graphene metallic, that is, without creating electronic (Anderson) localization, is experimentally challenging. Here, we show that the controlled addition of small amounts of covalently bonded hydrogen atoms is sufficient to induce a colossal enhancement of the SO interaction by three orders of magnitude. This results in a SHE at zero external magnetic fields at room temperature, with non-local spin signals up to 100 Ω; orders of magnitude larger than in metals. The non-local SHE is, further, directly confirmed by Larmor spin-precession measurements. From this and the length dependence of the non-local signal we extract a spin relaxation length of ∼1 μm, a spin relaxation time of ∼ 90 ps and a SO strength of 2.5 meV. © 2013 Macmillan Publishers Limited. All rights reserved.