has been attributed to the presence of uncontrolled surface oxides formed during fabrication which can introduce defects and impurities that create decoherence channels. Here, we develop an ab initio Shiba theory to investigate the microscopic origin of magnetic-induced decoherence in niobium thin film superconductors and the formation of native oxides. Our ab initio calculations encompass the roles of structural disorder, stoichiometry, and strain on the formation of decoherence-inducing local spin moments. With parameters derived from these first-principles calculations we develop an effective quasi-classical model of magnetic-induced losses in the superconductor. We identify d-channel losses (associated with oxygen vacancies) as especially parasitic, resulting in a residual zero temperature surface impedance. This work provides a route to connecting atomic scale properties of superconducting materials and macroscopic decoherence channels affecting quantum systems.