We study the motion of a particle sliding under the action of an external field on a stochastically fluctuating one-dimensional Edwards-Wilkinson surface. Numerical simulations using the single-step model shows that the mean-square displacement of the sliding particle shows distinct dynamic scaling behavior, depending on whether the surface fluctuates faster or slower than the motion of the particle. When the surface fluctuations occur on a time scale much smaller than the particle motion, we find that the characteristic length scale shows anomalous diffusion with [Formula presented] where [Formula presented] from numerical data. On the other hand, when the particle moves faster than the surface, its dynamics is controlled by the surface fluctuations and [Formula presented] A self-consistent approximation predicts that the anomalous diffusion exponent is [Formula presented] in good agreement with simulation results. We also discuss the possibility of a slow crossover toward asymptotic diffusive behavior. The probability distribution of the displacement has a Gaussian form in both the cases. © 2004 The American Physical Society.