In this talk I describe a new, first-principles-based theory of magnetic impurities on superconducting surfaces and multilayers. I show how the Green's function embedding technique, commonplace in multiple scattering theory, can be extended to the fully relativistic Bogoliubov-de Gennes equation in such systems. The resulting theory is used to study the Yu-Shiba-Rusinov (YSR) states in the atomic monomer and dimers of Mn on top of Nb surfaces. The results are compared to recent experimental findings and previous tight-binding calculations. We also investigate the formation of the YSR states in the presence of different magnetic configurations and exchange magnetic fields and study the effect of spin-orbit coupling as well.