Sesame cake and meal, byproducts of the sesame oil process industry and mainly used as feed and fertilizer, are often not optimally utilized and are wasted when the material could be used as a high-quality protein source. This research primarily emphasizes the preparation of a sesame protein-based adhesive with urea and glyoxal modification to use as a wood adhesive. The performance and characterization of the urea and glyoxal modified sesame protein adhesive (USP and GUSP, respectively) were measured precisely. After glyoxal was added, the water resistance of the GUSP adhesive was significantly enhanced, reaching the standard for Type II plywood. The formaldehyde emission test showed that the GUSP adhesive could be utilized as a formaldehyde-free wood adhesive, having a significantly lower than the demand of the E0 level (i.e., 0.5 mg/L). Furthermore, increasing the glyoxal content in the adhesives enhanced the thermal stability but not significantly. A substance with a crosslinking structure was formed from the reaction between the sesame protein and glyoxal, which enhanced the water resistance. Meanwhile, the fractured structure of the GUSP adhesive having a compact surface also was propitious to enhance the water resistance. Thus, the GUSP adhesive could be used as a novel adhesive in plywood fabrication.