In aiming to obtain highly flexible polymer composites with high dielectric performance, graphene/poly(vinylidene fluoride) (PVDF) composites with a multi-layered structure were proposed and prepared. Graphene sheets were prepared by reducing graphene oxide using phenylhydrazine, which could effectively alleviate aggregation of the graphene sheets. A two-step method, including solution casting and compression molding, was employed to fabricate the graphene/PVDF composites. The composites showed an alternative multi-layered structure of graphene sheets and PVDF. Due to their unique structure, the composites had an extremely low percolation threshold (0.0018 volume fraction of graphene), which was the lowest percolation threshold ever reported among PVDF-based polymer composites. A high dielectric constant of more than 340 at 100 Hz could be obtained within the vicinity of the percolation threshold when the graphene volume fraction was 0.00177. Above the percolation threshold, the dielectric constant continued to increase and a maximum value of as high as 7940 at 100 Hz was observed when the graphene volume fraction was 0.0177.