Softwood hemicelluloses could potentially be combined with cellulose and used in packaging materials. In the present study, galactoglucomannan (GGM) is adsorbed to wood cellulose nanofibers (CNF) and filtered and dried or hot-pressed to form nanocomposite films. The CNF/GGM fibril diameters are characterized by AFM, and the colloidal behavior by dynamic light scattering. Mechanical properties are measured in uniaxial tension for wet gels, dried films, and hot-pressed films. The role of GGM is particularly important for the wet gels. The wet gels of CNF/GGM exhibit remarkable improvement in mechanical properties. FE-SEM fractography and moisture sorption studies are carried out to interpret the results for hygromechanical properties. The present study shows that GGM may find use as a molecular scale cellulose binding agent, causing little sacrifice in mechanical properties and improving wet strength.