We report on the immersion of a spin-qubit encoded in a single trapped ion into a spin-polarized neutral atom environment, which possesses both continuous (motional) and discrete (spin) degrees of freedom. The environment offers the possibility of a precise microscopic description, which allows us to understand dynamics and decoherence from first principles. We observe the spin dynamics of the qubit and measure the decoherence times (T1 and T2), which are determined by the spin-exchange interaction as well as by an unexpectedly strong spin-nonconserving coupling mechanism.