We theoretically analyze contributions from the Kondo effect to the spin polarization and spin diffusion length in all-metal nonlocal spin valves. Interdiffusion of ferromagnetic atoms into the normal metal layer creates a region in which Kondo physics plays a significant role, giving discrepancies between experiment and existing theory. We start from a simple model and construct a modified spin drift-diffusion equation which clearly demonstrates how the Kondo physics not only suppresses the electrical conductivity but even more strongly reduces the spin diffusion length. We also present an explicit expression for the suppression of spin polarization due to Kondo physics in an illustrative regime. We compare this theory to previous experimental data to extract an estimate of the Elliot-Yafet probability for Kondo spin flip scattering of 0.7 ± 0.4, in good agreement with the value of 2/3 derived in the original theory of Kondo.