In the last few years, the design of marine propellers has significantly evolved. Basic potential flow methods were outclassed by simulation-based design optimization approaches fed by high-fidelity Computational Fluid Dynamics (CFD) calculations, often supported by Machine Learning (ML) based surrogate models to overcome computational resources’ limitations or comply with relatively short design deadlines. In most cases, only deterministic designs, i.e., for given functioning conditions, were addressed. However, in real functioning scenarios, propellers operate in conditions (e.g., inflow, rate of revolutions) that may have a certain level of uncertainty, or, from the geometrical point of view, they may be affected by tolerances that can nullify some of the advantages foreseen and expected by the optimization of geometrical details not sufficiently monitored and accurately handled during the manufacturing process. This uncertainty of the input parameters is reflected in the performance of the design. Therefore, a deterministic design approach, without considering the stochastic nature of inputs, may result excessively sensitive to slight variations of the operational conditions, leading to a final geometry that is not optimal in its real and uncertain functioning scenario. The cost of this approach consists of the computational effort required to quantify the uncertainties of the design, which may result prohibitive also when mid-fidelity solvers, like Boundary Element Methods (BEM) are employed in the SBDO. As in the case of deterministic design optimizations driven by high-fidelity codes, ML methodologies represent a computational booster of the procedure. Specifically, in this paper, deterministic and non-deterministic designs are carried out in the case of a conventional designs, considering uncertainties of the nominal functioning conditions. Specifically, in this paper, deterministic and non-deterministic designs are carried out in the case of a conventional propeller, considering uncertainties of the nominal functioning conditions. BEM calculations are used to train accurate ML-based surrogate models, which, in turn, support the evaluation of the uncertainties needed for non-deterministic optimization. Finally, optimal geometries from both approaches are tested against uncertain functioning conditions, leveraging high-fidelity CFD solvers (i.e., Reynolds-averaged Navier–Stokes) to prove the better response of the non-deterministic configurations.