The possibility of transporting spin information over long distances in graphene, owing to its small intrinsic spin-orbit coupling (SOC) and the absence of hyperfine interaction, has led to intense research into spintronic applications. However, measured spin relaxation times are orders of magnitude smaller than initially predicted, while the main physical process for spin dephasing and its charge-density and disorder dependences remain unconvincingly described by conventional mechanisms. Here, we unravel a spin relaxation mechanism for nonmagnetic samples that follows from an entanglement between spin and pseudospin driven by random SOC, which makes it unique to graphene. The mixing between spin and pseudospin-related Berrys phases results in fast spin dephasing even when approaching the ballistic limit, with increasing relaxation times away from the Dirac point, as observed experimentally. The SOC can be caused by adatoms, ripples or even the substrate, suggesting novel spin manipulation strategies based on the pseudospin degree of freedom.