© 2016, Nature Publishing Group. All rights reserved. The understanding of spin dynamics and relaxation mechanisms in clean graphene, and the upper time and length scales on which spin devices can operate, are prerequisites to realizing graphene-based spintronic technologies. Here we theoretically reveal the nature of fundamental spin relaxation mechanisms in clean graphene on different substrates with Rashba spin-orbit fields as low as a few tens of μeV. Spin lifetimes ranging from 50 picoseconds up to several nanoseconds are found to be dictated by substrate-induced electron-hole characteristics. A crossover in the spin relaxation mechanism from a Dyakonov-Perel type for SiO2 substrates to a broadening-induced dephasing for hBN substrates is described. The energy dependence of spin lifetimes, their ratio for spins pointing out-of-plane and in-plane, and the scaling with disorder provide a global picture about spin dynamics and relaxation in ultraclean graphene in the presence of electron-hole puddles.