Spin-phonon coupling is the main driver of spin relaxation and decoherence in solid-state semiconductors at finite temperature. Controlling this interaction is a central problem for many disciplines, ranging from magnetic resonance to quantum technologies. Spin relaxation theories have been developed for almost a century but often use a phenomenological description of phonons and their coupling to spin, resulting in a nonpredictive tool and hindering our detailed understanding of spin dynamics. Here, we combine time-local master equations up to the fourth order with advanced electronic structure methods and perform predictions of spin-phonon relaxation time for a series of solid-state coordination compounds based on both transition metals and lanthanide Kramers ions. The agreement between experiments and simulations demonstrates that an accurate, universal, and fully ab initio implementation of spin relaxation theory is possible, thus paving the way to a systematic study of spin-phonon relaxation in solid-state materials.