An understanding of hydrogen diffusion on metal surfaces is important not only for its role in heterogeneous catalysis and hydrogen fuel cell technology but also because it provides model systems where tunneling can be studied under well-defined conditions. Here we report helium spin-echo measurements of the atomic-scale motion of hydrogen on the Ru(0001) surface between 75 and 250 K. Quantum effects are evident at temperatures as high as 200 K, while below 120 K we observe a tunneling-dominated temperature-independent jump rate of 1.9 × 109 s-1, many orders of magnitude faster than previously seen. Quantum transition-state theory calculations based on ab initio path-integral simulations reproduce the temperature dependence of the rate at higher temperatures and predict a crossover to tunneling-dominated diffusion at low temperatures. However, the tunneling rate is underestimated, highlighting the need for future experimental and theoretical studies of hydrogen diffusion on this and other well-defined surfaces.