Engineered woods, plywood, particle board, and oriented strand board, are widely used as a low-cost wood replacement in many applications. Many of the currently used wood adhesives contain chemicals that are harmful to human health and the environment. Increasing environmental and human health concerns have made the development of safe bio-based adhesives a priority. In this study, two plant proteins, zein from corn and wheat gluten, were used to develop wood adhesives. To increase their bond strength, cellulose nanofibers were added to create nanocomposite adhesives and a crosslinking agent was also used. Single-lap shear test, flexural and internal bond tests were performed on dry and water-immersed samples to measure the bond strength. Fractured bond surfaces were studied using optical observation and scanning electron microscopy (SEM) to determine bond failure mechanisms. Thermal and chemical properties of the adhesives were evaluated using thermogravimetric analysis (TGA) and Fourier transform infrared spectroscopy (FTIR), respectively.