The influence of the carbohydrate-based wall matrix (glucose syrup, GS, and maltodextrin, MD21) and the storage temperature (4 °C or 25 °C) on the oxidative stability of microencapsulated fish oil was studied. The microcapsules (ca. 13 wt% oil load) were produced by spray-drying emulsions stabilized with whey protein hydrolysate (WPH), achieving high encapsulation efficiencies (>97%). Both encapsulating materials showed an increase in the oxidation rate with the storage temperature. The GS-based microcapsules presented the highest oxidative stability regardless of the storage temperature with a peroxide value (PV) of 3.49 ± 0.25 meq O2/kg oil and a content of 1-penten-3-ol of 48.06 ± 9.57 ng/g oil after six weeks of storage at 4 °C. Moreover, low-fat mayonnaise enriched with GS-based microcapsules loaded with fish oil and containing WPH as a film-forming material (M-GS) presented higher oxidative stability after one month of storage when compared to low-fat mayonnaise enriched with either a 5 wt% fish oil-in-water emulsion stabilized with WPH or neat fish oil. This was attributed to a higher protective effect of the carbohydrate wall once the microcapsules were incorporated into the mayonnaise matrix.