We investigate the influence of electron-phonon coupling on the superexchange interaction of magnetic insulators. Both the Holstein-Hubbard model where the phonons couple to the electron density, as well as an extended Su, Schrieffer, Heeger model where the coupling arises from modulation of the overlap integral are studied using exact diagonalization and perturbative methods. In all cases for both the adiabatic (but non-zero frequency) and anti-adiabatic parameter regions the electron-phonon coupling is found to enhance the superexchange. RI Grilli, Marco/C-6309-2009; Capone, Massimo/A-7762-2008