We have studied the energy dependence of the electron-phonon coupling strength on Bi(100). A fit of the temperature-dependent surface state linewidth results in a change of the coupling parameter lambda from 0.20+/-0.02 to 0.72+/-0.05 as the binding energy of the surface state increases from 70 to 330 meV. This result cannot be reconciled with the usual interpretation of lambda as the electron-phonon mass enhancement parameter at the Fermi energy. We suggest that this behavior is mainly caused by the strong energy dependence of the bulk density of states in this region.