We found that the optimized mixture of graphene and multilayer graphene, produced by the high-yield inexpensive liquid-phase-exfoliation technique, can lead to an extremely strong enhancement of the cross-plane thermal conductivity K of the composite. The "laser flash" measurements revealed a record-high enhancement of K by 2300% in the graphene-based polymer at the filler loading fraction f = 10 vol %. It was determined that the relatively high concentration of the single-layer and bilayer graphene flakes (~10-15%) present simultaneously with the thicker multilayers of large lateral size (~1 μm) were essential for the observed unusual K enhancement. The thermal conductivity of the commercial thermal grease was increased from an initial value of ~5.8 W/mK to K = 14 W/mK at the small loading f = 2%, which preserved all mechanical properties of the hybrid. Our modeling results suggest that graphene-multilayer graphene nanocomposite used as the thermal interface material outperforms those with carbon nanotubes or metal nanoparticles owing to graphene's aspect ratio and lower Kapitza resistance at the graphene-matrix interface. © 2012 American Chemical Society