In this study, mixed-structure carbon-magnetite nanocomposites were prepared by decorating of carbon nanofiber (CNF) surfaces with magnetite (Fe3O4) nanoparticles synthesized via reflux method and characterized. The compositions of CNF-Fe3O4 nanocomposites were varied using different amounts of CNF into the Fe3O4 synthesis medium as 25/75, 50/50, and 75/25 (w/w). These nanocomposites were then used as functional fillers to prepare flexible, thermoplastic polyurethane (TPU)-based electromagnetic interference (EMI) shielding composites by solution mixing method. Structural features of fillers, morphological, and electromagnetic properties of flexible composites were studied. It was found that the magnetite nanoparticles with the average size of 8-10 nm were formed and successfully covered the oxidized CNF surfaces. It was also found that the resulting CNF-Fe3O4 nanocomposites exhibited sufficiently high saturation magnetization (M-s) values compared to Fe3O4. These CNF-Fe3O4 nanocomposites were embedded into TPU phase by employing the weight percent of 20 wt%. The flexible TPU-CNF-Fe3O4 nanocomposite having the composition of 80-5-15 wt% showed the reflection loss (RL) value of -32 dB which signified that the composite material could absorb the 97 % of an incident electromagnetic wave at around 12.14 GHz.