The design of new solid electrolytes (SEs) hinges on identifying and tuning relevant descriptors. Phonons describe the atomic dynamics in crystalline materials and provide a basis to encode possible minimum energy pathways for ion migration, but anharmonic effects can be large in SEs. Identifying and controlling the pertinent phonon modes coupled most strongly with ionic conductivity, and assessing the role of anharmonicity, could therefore pave the way for discovering and designing new SEs via phonon engineering. Here, we investigate phonons in Na3PS4 and their coupling to fast Na diffusion, using a combination of neutron scattering, ab initio molecular dynamics (AIMD), and extended molecular dynamics based on machine-learned potentials. We identify that anharmonic soft-modes at the Brillouin zone boundary of the anharmonically stabilized cubic phase constitute key phonon modes that control the Na diffusion process in Na3PS4. We demonstrate how these strongly anharmonic phonon modes enable Na-ions to hop along the minimum energy pathways. Further, the quasi-elastic neutron scattering (QENS) measurements, supplemented with ab initio and machine-learned molecular dynamics simulations, probe the Na diffusivity and diffusion mechanism. These results offer detailed microscopic insights into the dynamic mechanism of fast Na diffusion and provide an avenue to search for further Na solid electrolytes.