The influence of lignocellulosic nanofibers (LCNF) additive on the inherent mechanical properties of submicron electrospun poly(vinyl alcohol) (PVA) fibers is reported. LCNF with a diameter of 25615 nm and a length of 220690 nm obtained from hemp shives were dispersed in aqueous PVA solutions to produce homogeneous nanocomposite fibers with 0, 5, and 10 w/w % LCNF loads in solid PVA. Tensile tests on mats show that LCNF additive causes up to sevenfold increase in stiffness and significant decrease in elongation at yield. AFM-based 3-point bending tests on single LCNF-doped fibers reveal up to 11.4 GPa Young’s modulus in the diameter range of 300 to 500 nm, indicating a 2.4 times increase compared to neat PVA fibers. Mechanical properties of both neat and LCNF-doped PVA fibers are found to be strongly size-dependent at lower fiber diameters, with Young’s modulus values exceeding 100 GPa at below 100 nm diameters. The results can be explained by extensive restructuration of hydrogen bonding network due to the LCNF additive.