The properties of surface plasmons localized at the interface between graphene and Kerr-type nonlinear substrates are investigated analytically. Although the relative propagation distance remains the same, the dispersion of graphene plasmons may be affected much by the inevitable nonlinear effect of substrates. Specifically, the wavelength of graphene plasmons can be tuned by adjusting the nonlinear permittivity of substrates.