The Maillard conjugation of whey protein isolate (WPI) by dry heat treatment (74% relative humidity at 60 °C) to either the water-soluble fraction of almond gum (SFAG) or flaxseed mucilage (SFM) was compared. Depending on the protein to polysaccharide ratio, carbohydrate type, and incubation time, different degrees of substitutions of the amino groups were obtained. The characterization of the conjugates by TNBS, SDS-PAGE, size exclusion chromatography, and circular dichroism analysis confirmed the formation of conjugates. SFAG was found to have less tendency for the formation of grafted WPI than SFM, which could be attributed to both the polysaccharide composition and/or a higher molecular weight. Ultimately, the emulsions stabilized by conjugates (pH 5.0 and 6.5) remained homogenous with no droplet size variation after heating, indicating that the conjugation of WPI to SFAG and SFM substantially improved its heat stability.