High-performance thermal interface materials (TIMs) often encounter the trade-off between high thermal conductivity and superior compliance. Herein, we report a graphene-based lamellar composite consisting of vertical graphene films and modified paraffin wax, fabricated by a layer-by-layer rolling assembly. Owing to the excellent deformability and confined flow of melted paraffin wax between graphene films, the composite shows a low contact thermal resistance of 17 K mm2 W-1 at 60 psi as a heat transfer interface, without leakage of paraffin wax. Due to the synergistic effect between the high heat capacity of paraffin wax and the high thermal conductivity of graphene films, the composite TIM yields an ultrahigh overall thermal conductivity of 789 W m-1 K-1 at 55 °C. When tested under a heat flux density of 30 W cm-2 on a simulated chip, the lamellar composite demonstrates a temperature rise much lower than that of a commercial TIM pad. The superior cooling efficiency indicates that the lamellar composite potentially offers a scalable and finely controllable design protocol for advanced TIMs to meet high-power heat dissipation requirements.