The intertwining between spin, charge, and lattice degrees of freedom can give rise to unusual macroscopic quantum states, including high-temperature superconductivity and quantum anomalous Hall effects. Recently, a charge density wave (CDW) has been observed in the kagome antiferromagnet FeGe, indicative of possible intertwining physics. An outstanding question is that whether magnetic correlation is fundamental for the spontaneous spatial symmetry breaking orders. Here, utilizing elastic and high-resolution inelastic x-ray scattering, we observe a c-axis superlattice vector that coexists with the 2×2×1 CDW vectors in the kagome plane. Most interestingly, between the magnetic and CDW transition temperatures, the phonon dynamical structure factor shows a giant phonon-energy hardening and a substantial phonon linewidth broadening near the c-axis wavevectors, both signaling the spin-phonon coupling. By first principles and model calculations, we show that both the static spin polarization and dynamic spin excitations intertwine with the phonon to drive the spatial symmetry breaking in FeGe.