This investigation aims to study the characteristics and release properties of lutein-loaded polyvinyl alcohol/sodium alginate (PVA/SA) nanofibers prepared by electrospinning. In order to increase PVA/SA nanofibers’ water-resistant ability for potential biomedical applications, the electrospun PVA/SA nanofibers were cross-linked with a mixture of glutaraldehyde and saturated boric acid solution at room temperature. The nanofibers were characterized using scanning electron microscopy (SEM) and X-ray diffractometer (XRD). Disintegration time and contact angle measurements testified the hydrophilicity change of the nanofibers before and after cross-linking. The lutein release from the nanofibers after cross-linking was measured by an ultraviolet absorption spectrophotometer, which showed sustained release up to 48 h and followed anomalous (non-Fickian) release mechanism as indicated by diffusion exponent value obtained from the Korsmeyer–Peppas equation. The results indicated that the prepared lutein-loaded PVA/SA nanofibers have great potential as a controlled release system.