The solubility of electrospun poly(vinyl alcohol) nanofiber mats (PVA(ES-NFM)) is strongly influenced by loading with nanocellulose (NC). The NC was derived from hemp shives obtained by steam explosion autohydrolysis followed by water and alkaline extraction, ball milling, and ultrasonication treatments. It was demonstrated for the first time that PVA(ES-NFM) does not disintegrate in aqueous medium after simple adding of NC without any additional chemical or physical modification (PVA(ES-NFM) NC). The structural and thermal studies on PVA(ES-NFM)NC indicated that enhanced stability in aqueous medium can be explained by interactions between surface groups of NC and PVA macromolecules as well as by reinforcing the effect of NCs. The experimental findings could be important for filtration applications in environments with high relative humidity.