The coupling of a spin to an underlying substrate is the basis for a plethora of phenomena. In the case of a metallic substrate, Kondo screening of the adatom magnetic moment can occur. As the substrate turns superconducting, an intriguing situation emerges where the pair breaking due to the adatom spins leads to Yu-Shiba-Rusinov bound states, but also intertwines with Kondo phenomena. Through scanning tunneling spectroscopy, we analyze the interdependence of Kondo screening and superconductivity. Our data obtained on single Fe adatoms on Nb(110) show that the coupling and the resulting YSR states are strongly adsorption site-dependent and reveal a quantum phase transition at a Kondo temperature comparable to the superconducting gap. The experimental signatures are rationalized by combined density functional theory and continuous-time quantum Monte-Carlo calculations to rigorously treat magnetic and hybridization effects on equal footing.