Polyrotaxane, owing to the special topological interlocked structure, has attracted more and more attention from researchers. In this paper, a new polyrotaxane derivative has been synthesized based on the polyrotaxane end capped by 2, 4-dinitrofluorobenzene (DNFB). And through cross-linking the polyrotaxane derivative meanwhile adding graphene filler, high dielectric constant elastomeric nanocomposite is fabricated according to percolation theory. SEM images show that the addition of polyvinylpyrrolidone (PVP) improves the dispersibility of graphene in the cross-linked matrix. The percolation threshold of composite with PVP-modified graphene is 2.45 vol.% and for unmodified composite it is 2.20 vol.%. Besides, the dielectric constant of composite with PVP-modified graphene increases sharply to 289.8 with graphene content of 2.35 vol.% which is 25 times higher than that of matrix. However, the dielectric loss of composite is just 0.46. What is more, the thermal stability of composites shows an obvious enhancement compared to the polymer matrix. And the composite films still exhibit great flexibility at room temperature.