Magnetic relaxation in coordination compounds is largely dominated by the interaction of the spin with phonons. Although a comprehensive understanding of spin-phonon relaxation has been achieved for mononuclear complexes, only a qualitative picture is available for polynuclear compounds. Large zero-field splitting and exchange coupling values have been empirically found to strongly suppress spin relaxation and have been used as the main guideline for designing molecular compounds with long spin lifetime, also known as single-molecule magnets, but no microscopic rationale for these observations is available. Here we fill this critical knowledge gap by providing a full first-principles description of spin-phonon relaxation in an air-stable Co(II) dimer with both large single-ion anisotropy and exchange coupling. Simulations reproduce the experimental relaxation data with excellent accuracy and provide a microscopic understanding of Orbach and Raman relaxation pathways and their dependency on exchange coupling, zero-field splitting, and molecular vibrations. Theory and numerical simulations show that increasing cluster nuclearity to just four cobalt units would lead to a complete suppression of low-temperature Raman relaxation. These results hold a general validity for polynuclear single-molecule magnets, providing a deeper understanding of their relaxation and revised strategies for their improvement.