We report the fabrication of water-stable electrospun polyethyleneimine (PEI)/polyvinyl alcohol (PVA) nanofibers that have super dye sorption capability. Electrospinning parameters including flow rate, applied voltage, and polymer concentration were optimized to obtain smooth and uniform PEI/PVA nanofibers. The nanofibers with a mean diameter of 490 ± 83 nm can be rendered water insoluble via crosslinking using glutaraldehyde vapor. The formed nanofibers with a smooth and uniform morphology before and after crosslinking were characterized using scanning electron microscopy, Fourier transform infrared spectroscopy, and mechanical property testing. The sorption capability of the PEI/PVA nanofibers was confirmed by UV-vis spectrometry. We show that the water-stable nanofibrous mats can effectively absorb methyl blue, which is a typical dye used in the printing and dyeing industry. The dye sorption kinetics and isotherm follow the pseudo-second-order model and the Langmuir model, respectively. The developed polymer nanofiber system has a great potential in decolorizing dyeing wastewater for environmental remediation applications.