The aim of the current study is to optimize the bead geometries of 80B2, namely, the bead height (BH) and bead width (BW), utilizing a mild steel substrate and a wire-arc additive manufacturing (WAAM) technique based on gas metal arc welding (GMAW). Single-layer depositions with different wire feed speed (WFS), voltage (V), and travel speed (TS) were accomplished by applying the Box–Behnken design methodology. Multivariable nonlinear regression models were developed and validated through ANOVA, revealing WFS as the most significant parameter influencing both BW and BH. The minimal influence of the error factor on each response proved the accuracy of the ANOVA findings. The favorable assessment of residual plots confirmed the appropriateness and reliability of the developed regression equations and ANOVA results. A metaheuristic Passing Vehicle Search (PVS) algorithm was applied for single-objective and multi-objective optimization, yielding a minimum BW of 5.874 mm and a maximum BH of 14.153 mm. Main effect and residual plots confirmed the accuracy and reliability of the predictive models. The parametric settings of WFS: 18 mm/min, TS: 7 mm/s, V: 19 V were obtained for simultaneous optimization of BW with 7.78 mm and BH with 10.87 mm. Pareto points were also generated, which provide non-dominated unique solutions. The study emphasizes the critical role of precise process parameter control in improving WAAM build quality and offers a robust framework for optimizing bead morphology, ultimately enhancing the efficiency and applicability of WAAM for structural component fabrication. These optimized parameters will be used in the future to manufacture a thin-walled, multi-layered structure.