Interleaf is often used to increase the interlaminar fracture toughness of carbon fiber/epoxy (CF/EP) composites, but it remains a challenge to develop high-performance interleaves that can greatly improve the toughness while simultaneously maintaining the in-plane properties. In this study, the carboxylated carbon nanotubes were uniformly decorated onto the surface of electrospun PA66 nanofibers by combination of ultrasonication and interfacial hydrogen bonding, and the obtained flexible nanofiber composite was served as interleaves in the CF/EP laminate. It is found that the modes I and II interlaminar fracture toughness of CNT-COOH/PA66 nanofiber interleaved laminate increases by 122 and 81% compared to the pristine CF/EP. Also, the flexural strength and flexural modulus was enhanced due to the reinforcing effect of the CNT-COOHs. The toughening mechanisms for both modes I and II fracture are investigated in detail based on the morphology of the delamination surface of the laminates.