The effect of spin-orbit coupling on the electron-phonon interaction in a (4/3)-monolayer of Pb on Si(111) is investigated within the density-functional theory and linear-response approach in the mixed-basis pseudopotential representation. We show that the spin-orbit interaction produces a large weakening of the electron-phonon coupling strength, which appears to be strongly overestimated in the scalar relativistic calculations. The effect of spin-orbit interaction is largely determined by the induced modification of Pb electronic bands and a stiffening of the low-energy part of phonon spectrum, which favor a weakening of the electron-phonon coupling strength. The state-dependent strength of the electron-phonon interaction in occupied Pb electronic bands varies depending on binding energy rather than electronic momentum. It is markedly larger than the value averaged over electron momentum because substrate electronic bands make a small contribution to the phonon-mediated scattering and agrees well with the experimental data.