In the past two decades, research on electrospinning has boomed due to its advantages of simple process, small fiber diameter, and special physical and chemical properties. The electrospun fibers are collected in a non-woven state in most cases (electrospun non-woven fabrics, ESNWs), which renders the electrospinning method an optimum approach for non-woven fabric manufacturing on the nano-scale. The present study establishes a convenient preparation procedure for converting water-soluble dialdehyde cellulose (DAC) into DAC-based electrospun non-woven fabrics (ESNWs) reinforced with poly(vinyl alcohol) (PVA). The aldehyde content, which was quantified by colorimetry using Schiff’s reagent, was 11.1 mmol per gram of DAC, which corresponds to a conversion yield of ca. 90%. DAC is fully water-soluble at room temperature between 10 and 30 wt%, and aqueous solutions turn into hydrogels within 24 h. To overcome gelation, NaHSO 3, which forms bisulfite adducts with aldehyde functions, was added to the DAC and its concentration was optimized at 1 wt%. The electrospun (ES) dope containing 5 wt% DAC, 5 wt% PVA, and 1 wt% NaHSO 3 in an aqueous solution was successfully transformed into ESNW, with an average fiber diameter of 345 ± 43 nm. Post-spinning treatment with excess hexamethylene diisocyanate was performed to insolubilize the ESNW materials. The occurrence of this chemical conversion was confirmed by energy-dispersive X-ray elemental analysis and vibrational spectra. The cross-linked DAC/PVA ESNW retained its thin fiber network upon soaking in distilled water, increasing the average fiber diameter to 424 ± 95 nm. This suggests that DAC/PVA-ESNWs will be applicable for incorporation or immobilization of biologically active substances.