We compute the phonon dispersion, density of states, and the Gruneisen parameters of bulk palladium in the combined density functional theory (DFT) and dynamical mean-field theory (DMFT). We find good agreement with experimental results for ground state properties (equilibrium lattice parameter and bulk modulus) and the experimentally measured phonon spectra. We demonstrate that at temperatures $T lesssim 20~K$ the phonon frequency in the vicinity of the Kohn anomaly, $omega_{T1}({bf q}_{K})$, strongly decreases. This is in contrast to DFT where this frequency remains essentially constant in the whole temperature range. Apparently correlation effects reduce the restoring force of the ionic displacements at low temperatures, leading to a mode softening.