PVA hydrogels with anisotropic structures have many biomedical applications; however, the hydrophilicity of PVA nanofibers degrades their mechanical properties, and the residual unreacted chemical crosslinkers are disadvantageous for medical use. Therefore, maintaining the stability of aqueous solutions without using crosslinkers is essential while synthesizing electrospun anisotropic PVA nanofibers. Herein, we developed a novel fabrication method for synthesizing tough, anisotropic, and chemical-crosslinker-free nanofibrous cryogels composed of poly(vinyl alcohol) (PVA) and glycerol (Gly) via electrospinning in conjunction with freeze-thawing treatment. Wide-angle X-ray diffraction, attenuated total reflection Fourier-transform infrared spectroscopy, and differential scanning calorimetry analysis revealed an enhanced crystallinity of the PVA and hydrogen bonds in the PVA/Gly nanofibers after freeze-thawing, thereby leading to improved stability of the PVA/Gly nanofiber in water. The scanning electron microscopy observation and tensile tests revealed that the addition of Gly improved both the orientation and the mechanical properties. The values of the toughness parallel and vertical to the fiber axis direction were 4.20 +/- 0.63 MPa and 2.17 +/- 0.27 MPa, respectively, thus revealing the anisotropy of this mechanical property. The PVA/Gly nanofibrous cryogel consisted of physically crosslinked biocompatible materials featuring toughness and mechanical anisotropy, which are favorable for medical applications including tissue engineering.