Poly(ethylene oxide) (PEO) nanofiber mats were produced by electrospinning. Biobased cellulose nanocrystals (CNCs) and cellulose nanofibrils (CNFs) as reinforcement nanofillers were also added to the polymer to produce composite nanofiber mats. The effects of the two cellulose nanofillers on the rheological properties of the PEO solutions and the microstructure, crystallization, and mechanical properties of the mats were systematically compared. The microstructural disparity between the CNCs and CNFs led to significant differences in the solution viscosity, nanofiber morphology and microstructure of the composite nanofiber mats. A unique shish-kebab-like crystalline structure was discovered in both pure and filled PEO nanofibers. Both CNCs and CNFs showed strong reinforcing effects on the nanofiber mats.