In this work, nanofibers of poly(vinyl alcohol) reinforced with cellulose nanofibrils were produced by electrospinning. The effects of applied voltage, polymer concentration and injection rate, tip-to-collector distance, rotation speed of the collector, and relative humidity on morphology were investigated by scanning electron microscopy. The reinforcing capability of cellulose nanofibrils was investigated by tensile tests. Thermogravimetry, transmission electron microscopy and Fourier transform infrared spectroscopy-attenuated total reflectance analyses were also carried out in order to characterize the presence, orientation and reinforcing effect of the cellulose nanofibrils. Scanning electron microscopy results showed that fiber structure is strongly affected by the electrospinning conditions. Thinner fibers are favored by decreasing viscosity, polymer injection rate, high rotation speed and high relative humidity. Whereas increasing the applied voltage favors the formation of beaded fibers. The reinforced composites had a 2.4-fold increase in their mechanical properties by addition of only 6.6 wt% of cellulose nanofibrils without major changes in elongation at break.