Cellulose nanocrystal (CNC) reinforced poly(vinyl alcohol) (PVA) hydrogels with a water content of ∼92% were successfully prepared with glutaraldehyde (GA) as a cross-linker. The effects of the CNC content on the thermal stability, swelling ratio and mechanical and viscoelastic properties of the cross-linked hydrogels were investigated. The compressive strength at 60% strain for the hydrogels with 1 wt% CNCs increased by 303%, from 17.5 kPa to 53 kPa. The creep results showed that the addition of CNCs decreased the creep elasticity due to molecular chain restriction. The almost complete strain recovery (∼97%) after fixed load removal for 15 min was observed from the hydrogels with CNCs, compared with 92% strain recovery of the neat cross-linked PVA hydrogels. The incorporation of CNCs did not affect the swelling ratio and thermal stability of the hydrogels. These results suggest the cross-linked CNC-PVA hydrogels have potential for use in biomedical and tissue engineering applications.