Flexible dielectric polymer composites with high dielectric permittivity and low dielectric loss have many applications in different areas of electronic industry. In this paper, we propose synthesis of flexible dielectric materials with efficient dielectric properties. We increased dielectric efficiency of poly(vinyl alcohol) by reinforcement of conducting graphene and rutile titania fillers in different weight fractions. The superiority of this method is that synthesized three phase graphene/titania/poly(vinyl alcohol) nanocomposite films have high dielectric permittivity, low dielectric loss and are flexible. Our results show that graphene/titania/poly(vinyl alcohol) with weight/weight fraction of 3:20:100 bears dielectric permittivity of 330 at 20 Hz that is about 36 times larger than that of neat PVA at same frequency. At this frequency above mentioned graphene/titania/poly(vinyl alcohol) nanocomposite has loss tangent of 4.39 acceptable for dielectrics in embedded capacitors and AC conductivity of 1.6 × 10−6 Sm−1 that is much greater than that of neat PVA i.e; 6.5 × 10−9 Sm−1. Complex impedance spectroscopy, complex electric modulus and Cole-Cole plots of synthesized graphene/titania/poly(vinyl alcohol) nanocomposite films further confirm its better capacitive performance. Keywords: Ceramics, Polymer, Dielectric response, Impedance spectroscopy, AC conductivity