Fabricating the thermally conductive composites through incorporating fillers into polymer matrix is usually at the sacrifice of the fracture toughness. To resolve such contradiction, this work proposed a feasible but highly efficient method of constructing the thermally conductive path in the epoxy composite at extremely low filler content. The polyvinylpyrrolidone (PVP) modified carbon nanofibers (P-CNFs) were coated on the three-dimensional (3D) framework surface of the melamine foam (MF), then the epoxy resin was impregnated into the [email protected]–CNF. The results showed that the assembled structure of [email protected] could be well reserved in the epoxy composite. Consequently, at extremely low P–CNF content (0.8 wt%), the [email protected]–CNF/EP sample shows the largely enhanced thermal conductivity (0.4 W/m·K) and glass transition temperature (167 °C) compared with the pure epoxy sample (0.2 W/m·K and 162 °C). Specifically, the composite sample also shows the apparently enhanced fracture toughness. Therefore, it is believed that coating CNFs on the 3D interconnected framework of MF is a promising way to prepare the epoxy composites with good comprehensive properties.