We present a tunnel spectroscopy study of single PbS Quantum Dots (QDs) as function of temperature and gate voltage. Three distinct signatures of strong electron-phonon coupling are observed in the Electron Tunneling Spectrum (ETS) of these QDs. In the shell-filling regime, the $8times$ degeneracy of the electronic levels is lifted by the Coulomb interactions and allows the observation of phonon sub-bands that result from the emission of optical phonons. At low bias, a gap is observed in the ETS that cannot be closed with the gate voltage, which is a distinguishing feature of the Franck-Condon (FC) blockade. From the data, a Huang-Rhys factor in the range $Ssim 1.7 - 2.5$ is obtained. Finally, in the shell tunneling regime, the optical phonons appear in the inelastic ETS $d^2I/dV^2$.