Surface modification of cellulose nanocrystals (CNCs) offers a sustainable route to enhance their interfacial compatibility and functionality in CNCs-stabilized polymer latexes. Here, CNCs were hydrophobically modified through covalent grafting of octylamine onto aldehyde-functionalized CNCs produced by periodate oxidation. CNCs with different degrees of octylamine substitutions all remained colloidally stable in water but exhibited different surface hydrophobicity. When employed as stabilizers for waterborne polyhydroxyurethane (PHU) latexes, octylamine modified CNCs (oCNCs) significantly reduced droplet and latex diameters compared to pristine CNCs, demonstrating the critical role of surface hydrophobicity in Pickering stabilization. Among the modified samples, oCNCs with the lowest degree of modification provided the most effective reinforcement in PHU/oCNC nanocomposite adhesives, achieving a 60% increase in adhesion strength and a 54% increase in adhesion energy compared to pristine CNC-stabilized PHU latexes with 9 wt.% CNCs. Increasing oCNCs loading to 17 wt.% further improved Tak adhesion strength to 1.0 MPa without sacrificing extensibility. The enhanced performance was attributed to optimized hydrophilic–hydrophobic balance and strong interfacial adhesion between oCNCs and the PHU matrix. This work establishes a simple and scalable chemical modification strategy for tailoring CNCs surface properties, enabling their dual role as stabilizers and reinforcements in high-performance, waterborne, bio-based polyurethane adhesives.