Using kinetic Monte Carlo simulations we have investigated the diffusion of particles over a lattice with moving atoms in the framework of a simple lattice-gas model of a reconstructive surface. The particle migration over the static and dynamic lattices differs considerably. The dynamic lattice reconstruction changes substantially the particle diffusion coefficient. The Arrhenius dependencies are quantitatively different. An interesting peculiarity of the particle migration is the formation of defectons--local lattice deformations around the adsorbed particles. In certain ranges of the system parameters (jump rates of the substrate atoms and adsorbed particles) the adsorbed particles cause local displacements of the nearest substrate atoms, resulting in deeper adsorption sites and lower jump rates. Such particle self-trapping produces a characteristic minimum on the Arrhenius dependencies.