Its hydrophilic property and poor water resistance prevent the application of starch in electrospun nanofibers for biomedical applications. In this paper, we apply a periodate oxidation-adipic acid dihydrazide crosslinking strategy to electrospun starch nanofibers and develop a new nanofiber material with excellent mechanical strength, superior water resistance, and excellent cytocompatibility. The crosslinked starch nanofiber membranes exhibit a Young's modulus up to 2.65 MPa in the wet state, can maintain 91.0% of their initial mass after four weeks' incubation in simulated body fluid, and do not cause toxicity to L929 fibroblast cells. The control nanofibers prepared with a conventional glutaraldehyde crosslinking strategy show only a 60 kPa Young's modulus, retain only 31.9% of their initial mass after four weeks in simulated body fluid, and cause toxicity to cells. The crosslinked starch nanofibers with high mechanical strength, excellent water resistance and good biocompatibility are promising for biomedical applications.