We study the strength of the electron-phonon interaction on Fe single adatoms on MgO/Ag(100) based on many-body \textit{ab-initio} spin collinear calculations. In particular, we analyze the relative importance of the substrate and, among other results, we conclude that the interface electron state of Ag(100) plays a prominent role in determining the electron-phonon coupling of localized Fe electron states. The analysis of the hybridization of the adatom with the substrate reveals qualitative differences for even or odd coverages of MgO, affecting significantly the spectral structure and strength of the electron-phonon coupling. Our calculations indicate that the electron-phonon interaction is very strong for $\le$~1 layers of MgO, while it is sharply suppressed for larger coverages, a trend that is consistent with recent experimental findings.