We elucidate the origin of the phonon-mediated superconductivity in 2H-NbS2 using the ab initio anisotropic Migdal-Eliashberg theory including Coulomb interactions. We demonstrate that superconductivity is associated with Fermi surface hot spots exhibiting an unusually strong electron-phonon interaction. The electron-lattice coupling is dominated by low-energy anharmonic phonons, which place the system on the verge of a charge density wave instability. We also provide definitive evidence for two-gap superconductivity in 2H-NbS2, and show that the low- and high-energy peaks observed in tunneling spectra correspond to the Γ- and K-centered Fermi surface pockets, respectively. The present findings call for further efforts to determine whether our proposed mechanism underpins superconductivity in the whole family of metallic transition metal dichalcogenides.