This study developed and evaluated plant-based mayonnaise formulations in which egg yolk was replaced with aquafaba (15–25%) and stabilized with gum tragacanth (0.3–1.0%). Formulations were prepared using canola oil and stored at 4 °C for 28 days. Aquafaba extract was characterized for total phenolic content (TPC) and total flavonoid content (TFC), while mayonnaise samples were assessed for physicochemical composition, creaming index, antioxidant activity, viscosity, texture, sensory properties, and microbiological stability. Total phenolic content (TPC) rose from 17.52 mg GAE/g at 10 µg to 135.34 mg GAE/g at 100 µg (p < 0.05), while total flavonoid content (TFC) increased from 76.95 to 192.42 mg TE/g over the same concentration range. These increases demonstrate the high antioxidant potential of aquafaba extract. The 25% aquafaba + 1% gum tragacanth formulation (T3) showed the highest protein content, viscosity, firmness, and antioxidant capacity, with improved storage stability compared to the control. FTIR analysis identified functional groups such as phenols, esters, and carboxylic acids, suggesting contributions to antioxidant activity and emulsion stability. Sensory evaluation indicated strong acceptance for T3. These results demonstrate that aquafaba combined with gum tragacanth can effectively replace egg yolk while maintaining desirable quality attributes.