Graphene flakes with giant shape anisotropy are extensively used to establish connectedness electrical percolation in various heterogeneous systems. However, the percolation behaviour of graphene flakes has been recently predicted to be far more complicated than generally anticipated on the basis of excluded volume arguments. Here we confirm experimentally that graphene flakes self-assemble into nematic liquid crystals below the onset of percolation. The competition of percolation and liquid crystal transition provides a new route towards high-k materials. Indeed, near-percolated liquid-crystalline graphene-based composites display unprecedented dielectric properties with a dielectric constant improved by 260-fold increase as compared with the polymer matrix, while maintaining the loss tangent as low as 0.4. This performance is shown to depend on the structure of monodomains of graphene liquid-crystalline phases. Insights into how the liquid crystal phase transition interferes with percolation transition and thus alters the dielectric constant are discussed.