The applicability of cellulose nanofibrils (CNFs) as viscosifying agent in a starch-reduced low-fat mayonnaise and in an oil-reduced full-fat mayonnaise has been considered. For low-fat mayonnaise a 50 wt% reduction in the ordinary starch content was performed, while for full-fat mayonnaise, the oil content was reduced from 79 to 70 wt%. To study if the stability was affected when CNFs were added, analyses as visual and accelerated stability tests, droplet size measurements and rheology studies, determining the shear viscosity, and the loss and storage moduli, were conducted after 1 day, 1 week and 1 month of storage in room temperature. Even though changes in droplet size distributions and rheological properties indicated some coalescence, the visual stability was not changed after 1 month of storage for any of the samples. The decrease in viscosity and moduli inflicted by reduction of starch or fat, could be regained by the addition of CNFs at 0.75 wt % and 0.42 wt %, respectively. Based on the results in this work, mayonnaise with reduced starch or fat content can be produced when CNFs are used as a viscosifying agent.