A novel two-step route to prepare graphene aerogel (GA)/poly(vinyl alcohol) (PVA) composites with exceptional dielectric performance is reported. The composites obtained from the initial unidirectional freeze casting possess a highly-aligned, conducting graphene skeleton with an ultralow density, a high porosity and remarkable thermal stability, showing ultrahigh dielectric constants combined with moderate losses. The losses are significantly reduced by means of PVA barriers introduced between the neighboring conductive main skeletons of the aligned GA/PVA networks in the 2^nd freeze casting process. The insulating barriers effectively block the current leakage by removing the transversely interconnected, conductive ligaments. The compaction of barrier-shielded, porous GA/PVA composites yield fully consolidated, solid composites which deliver both exceptional dielectric constants and very stable, low losses. The approach developed here paves the way for rational design and assembly of GA/PVA composites as a lightweight, tunable and high-performance dielectric material, satisfying various requirements for emerging applications.