Among various nanomaterials, cellulose nanocrystals (CNCs) are regarded as the most suitable reinforcing fillers for hydrogels owing to their high dispersibility in water and favorable hydrogen bonding with water-dispersible polymers. Herein, CNC-laden polyvinyl alcohol (PVA)/borax (P/CNC) hydrogels were prepared by solution mixing, and their mechanical and rheological properties were investigated in terms of CNC loading of 0–60 w/w%. PVA/borax hydrogels are known to exhibit self-healing ability based on the dynamic nature of the borate–diol complex, which is dependent on the rheological response because the rheological chain dynamics dominantly affect the self-healing process. In mechanical testing, the Young’s modulus of the P/CNC hydrogels sharply increased above 40 w/w% CNC, indicating that the stiffening effect of CNC was enhanced above the critical loading. From a rheological perspective, the increases in the viscosity and storage modulus were further accelerated above 40 w/w%. In particular, the chain flow relaxation time (τf), a quantitative parameter closely related to the self-healing performance, was observed for the P/CNC hydrogels with CNC amounts of 0−40 w/w% (1.6−97.3 s); whereas, there is no τf for the P/CNC hydrogels with 45−60 w/w% CNC within a reasonable time scale we observed at 25 °C. Consequently, the incorporation of less than 40 w/w% CNCs affords high mechanical stiffness while maintaining self-healing ability.