A decadal-scale deformation transient preceding the 2011 Mw 9 Tohoku-oki, Japan, earthquake was reported from continuous GPS data and interpreted as accelerating aseismic slip on the Japan Trench megathrust. Given the unprecedented nature of this transient, independent confirmation of accelerating slip is required. Here we show that changes in the recurrence intervals of repeating earthquakes on the Japan Trench megathrust in the period 1996 to 2011 are consistent with accelerating slip preceding the Tohoku-oki earthquake. All sequences of repeating earthquakes with statistically significant trends in recurrence interval (at 95% confidence) offshore south central Tohoku occurred at an accelerating rate. Furthermore, estimates of the magnitude of slip acceleration from repeating earthquakes are consistent with the completely independent geodetic estimates. From a joint inversion of the GPS and seismicity data, we infer that a substantial portion of the megathrust experienced accelerating slip, partly surrounding the eventual rupture zone of the Mw 9 earthquake.