Spider silk-inspired hydrogen-bond (H-bond) cross-linking has recently been shown to enable polymers, e.g., poly(vinyl alcohol) (PVA), to achieve high strength in combination with large ductility and great toughness by adding small H-bond cross-linkers. Unfortunately, the correlation of H-bond cross-linking to the microstructure and mechanical performances of the resultant polymers remains unclear. Herein, we prepare strong and tough nanostructured PVA composites with inositol (IN) molecules as cross-linkers. The addition of 1.0 wt % of IN increases the yield strength (σ_y) of PVA up to 148 MPa (by ∼31%), in combination with appreciable increases in the break strain (by 250%) and toughness (by 3.6-fold) because of dynamic physical cross-linking and crystalline grain refinement. We show that there exists a close but simple correlation between the H-bond cross-linking density (n_e) and σ_y, the chain movement (e.g., glass transition temperature (T_g), relaxation activation energy (E_a)) and the crystalline grain size (L), namely, σ_y ∝ n_e, T_g, E_a, and 1/L. This work casts light on the governing effect of H-bonding cross-linking on the microstructure and mechanical properties of PVA and unveils its correlation to mechanical properties, chain dynamics, and crystallization for the first time. These exciting findings open up many new opportunities for creating strong, tough, and ductile polymeric materials.