PVA/SWNT composite fibers demonstrate superior tensile strength, modulus, and toughness properties of 4.9 GPa, 128 GPa and 202 J/g, respectively. By tailoring the degree of undercooling of PVA during solution preparation, the interfacial crystallization of PVA in the vicinity of SWNT was promoted. Wide-angle X-ray diffraction (WAXD) shows that the interphase polymer structure is distinct from the bulk polymer structure (i.e. the change in crystallization behavior of the PVA at the interphase region). The proposed new PVA unit cell based on the X-ray diffraction evidence suggested a more adjacent PVA chain locations and shorter inter-chain hydrogen bonding distance compared to the regular PVA unit cell, indicating a denser packing around SWNT. The formation of this crystalline PVA coating around the SWNT surface leads to a significant increase of the stress transfer between the polymer matrix and nano-filler, and results in the excellent mechanical properties of the composite fibers.