We review the problem of spin decoherence of magnetic atoms deposited on a surface. Recent breakthroughs in scanning tunnelling microscopy (STM) make it possible to probe the spin dynamics of individual atoms, either isolated or integrated in nanoengineered spin structures. Transport pump and probe techniques with spin polarized tips permit measuring the spin relaxation time T1, while novel demonstration of electrically driven STM single spin resonance has provided a direct measurement of the spin coherence time T2 of an individual magnetic adatom. Here we address the problem of spin decoherence from the theoretical point of view. First we provide a short general overview of decoherence in open quantum systems and we discuss with some detail ambiguities that arise in the case of degenerate spectra, relevant for magnetic atoms. Second, we address the physical mechanisms that allows probing the spin coherence of magnetic atoms on surfaces. Third, we discuss the main spin decoherence mechanisms at work on a surface, most notably, Kondo interaction, but also spin–phonon coupling and dephasing by Johnson noise. Finally, we briefly discuss the implications in the broader context of quantum technologies.