We reveal how symmetry-protected nodal points in topological semimetals may be promoted to pairs of generically stable exceptional points (EPs) by symmetry-breaking fluctuations at the onset of long-range order. This intriguing interplay between non-Hermitian (NH) topology and spontaneous symmetry breaking is exemplified by a magnetic NH Weyl phase spontaneously emerging at the surface of a strongly correlated three-dimensional topological insulator, when entering the ferromagnetic regime from a high-temperature paramagnetic phase. Here, electronic excitations with opposite spin acquire significantly different lifetimes, thus giving rise to an anti-Hermitian structure in spin that is incompatible with the chiral spin texture of the nodal surface states, and hence facilitate the spontaneous formation of EPs. We present numerical evidence of this phenomenon by solving a microscopic multiband Hubbard model nonperturbatively in the framework of dynamical mean-field theory.