Today, the vast majority of wood adhesives are prepared from fossil-based polymers and many of them contain hazardous components, e.g., formaldehyde. Less hazardous, bio-based wood adhesives have been predominant in the wood-bonding processes until the twentieth century, but fossil-based adhesives replaced them due to their advantageous property-price ratio. With the growing environmental concern there is an urge to develop bio-based and harmless substitutes. Hemicelluloses, among other bio-based polymers, have been proposed as possible renewable resources for wood-adhesive components. In this study, we valorise hemicelluloses, a biproduct from a pulping process, as the main component in wood adhesives. Hemicelluloses themselves do not exhibit sufficient bonding performance, but excellent bond strength and water resistance were obtained in combination with a bio-based polymer with higher molecular weight. Furthermore, we investigate the interactions within the adhesive components and between the adhesive and wood. The current study constitutes an example on how sidestreams from the pulp industry can be used as a component in fully bio-based wood adhesives in the quest for a more sustainable society.