In this paper, the Surface Plasmon Polariton (SPP) dispersion relation in the TM polarization for the plane interface between a homogeneous dielectric medium (with constant εd) and a gradedpermittivity (i.e. nonhomogeneous) plasmonic medium (with dielectric function εp(z)) is obtained where ‘z’ is normal coordinate to the interface. For small variation of εp(z) it is revealed that the dispersion relation is related to the derivative of εp(z) at the interface and when εp becomes constant or when its derivative at the interface is zero the well-known dispersion relation for homogeneous plasmonic medium is obtained. For the case where εp(z) depends linearly on z, the dispersion relation is obtained. It is seen that two branches appear. The upper branch has a free-space-like behavior at small wavenumbers. Inclusion of frequency dependence in the εp(z) through Drude model, reveals that the upper branch has negative-value group velocity at intermediate wavenumbers. The results show that non-homogeneity of the plasmonic medium offers a good tunability to control dispersion relation and SPP group velocity.