The rheological characteristics of a physical gelation system, in which cellulose nanocrystals (CNCs) induced the entanglement of poly(acrylic acid) (PAA) chains and partial hydrophobic association of octylphenol polyoxyethylene acrylate (OP-10-AC) branches in a micellar solution of sodium dodecyl sulfate (SDS), were investigated. The gelation time of the physical gels decreased as the CNC content and number of hydrophobic branch units increased. At the gel point, the storage modulus (G') and loss modulus (G") followed the same frequency dependence (G' ≈ G" ≈ ωⁿ), where the hydrophobic moieties attached to the side chains had a significant impact on the values of viscoelastic exponent (n). Beyond the gel point, the initial polymer solution was transformed to a solid-like gel, and the strength of the gel network was governed by associations between both the CNCs and hydrophobic groups. The evolution of the viscoelasticity during the gel-sol transition was monitored, demonstrating that due to a reversible arrangement of the hydrophobic units, a large proportion of physical cross-links dissociated under a thermal trigger and were reversibly reformed when the solution was cooled, while no such partial recovery was observed in the case of the single CNC-induced network systems (with no hydrophobic branches).