We introduce a fully ab initio theory for inelastic scattering of any atom from any surface exciting single phonons, and apply the theory to helium scattering from Nb(100). The key aspect making our approach general is a direct first-principles evaluation of the scattering atom-electron vertex. By correcting misleading results from current state-of-the-art theories, this fully ab initio approach will be critical in guiding and interpreting experiments that adopt next-generation, nondestructive atomic beam scattering. © 2024 American Physical Society.