Natural cork stopper manufacturing produces a significant amount of cork waste, which is granulated and combined with synthetic glues for use in a wide range of applications. There is a high demand for using biosourced polymers in these composite materials. In this study, xanthan gum (XG) and chitosan (CS) were investigated as possible natural binders for cork. Xanthan gum was oxidized at two different aldehyde contents as a strategy to improve its water resistance. This modification was studied in detail by 1H and 13C nuclear magnetic resonance (NMR), and the degree of oxidation was determined by the hydroxylamine hydrochloride titration method. The performance of the adhesives was studied by tensile tests and total soluble matter (TSM) determinations. Xanthan gum showed no water resistance, contrary to oxidized xanthan gum and chitosan. It is hypothesized that the good performance of oxidized xanthan gum is due to the reaction of aldehyde groups—formed in the oxidation process—with hydroxyl groups on the cork surface during the high temperature drying. Combining oxidized xanthan gum with chitosan did not yield significant improvements.