Double nanoemulsions (DEs), containing pomegranate peel extract (PPE) stabilized with/without carboxymethyl cellulose (CMC), were used to prepare reduced-fat and functional mayonnaise samples. The effect of substituting oil in mayonnaise with DEs at different levels (5, 10, and 20%) was evaluated in terms of physicochemical properties, stability, color characteristics, sensory evaluation, and rheological behavior. The results revealed that the use of pomegranate peel extract encapsulated within double emulsion (PPE-DE) and PPE-DE stabilized with CMC (CMC/PPE-DE) in mayonnaise had significant effects on the physicochemical characteristics during storage. All mayonnaise samples had physical and heat stability more than 99%, and the samples containing CMC/PPE-DE exhibited higher stability than that containing PPE-DE. Regarding color attributes, replacing oil with DEs increased the lightness and decreased the yellowness and greenness of the mayonnaise samples as compared to control mayonnaise made without DEs. Furthermore, sensory evaluation of all mayonnaise formulations presented satisfactory acceptance; however, the mayonnaise with CMC/PPE-DE 10% was the best. Eventually, the rheological measurements indicated that all mayonnaise samples exhibited a non-Newtonian, shear-thinning flow behavior, making it more applicable to the food industry.