Single magnetic atoms, and assemblies of such atoms, on non-magnetic surfaces have recently attracted attention owing to their potential use in high-density magnetic data storage and as a platform for quantum computing. A fundamental problem resulting from their quantum mechanical nature is that the localized magnetic moments of these atoms are easily destabilized by interactions with electrons, nuclear spins and lattice vibrations of the substrate. Even when large magnetic fields are applied to stabilize the magnetic moment, the observed lifetimes remain rather short (less than a microsecond). Several routes for stabilizing the magnetic moment against fluctuations have been suggested, such as using thin insulating layers between the magnetic atom and the substrate to suppress the interactions with the substrate's conduction electrons, or coupling several magnetic moments together to reduce their quantum mechanical fluctuations. Here we show that the magnetic moments of single holmium atoms on a highly conductive metallic substrate can reach lifetimes of the order of minutes. The necessary decoupling from the thermal bath of electrons, nuclear spins and lattice vibrations is achieved by a remarkable combination of several symmetries intrinsic to the system: time reversal symmetry, the internal symmetries of the total angular momentum and the point symmetry of the local environment of the magnetic atom.