Electrically conductive and magnetically permeable carbon nanofiber-based composites were developed using the electrospinning with subsequent heat treatment. The composite nanofiber contains a variable composition of magnetite nanoparticles with two different size regimes, ranging from superparamagnetic (10-20nm) to ferromagnetic (20-30nm). The composite nanofibers are then characterized using Scanning/Transmission Electron Microscopy, X-Ray Diffractometry, Raman Spectroscopy, four-point probe, and a Superconducting Quantum Interference Device. Electromagnetic Interference Shielding Effectiveness of pristine carbon nanofibers as well as electromagnetic composite nanofibers are examined in the X-band frequency region. Higher degree of graphitization, electrical conductivity, and magnetic strength are obtained for nanocomposites containing larger magnetite nanoparticles (20-30nm). A transition from superpartamagnetic to ferromagnetic characteristics is observed during nanocomposite processing. Electromagnetic Interference Shielding Effectiveness of as high as 68dB (in the working frequency of 10.4GHz) is observed for composite nanofibers fabricated with larger magnetite nanoparticles carbonized at 900 degrees C.