Marine propellers often function under uncertain conditions such as variable inflow, rate of revolution, and manufacturing tolerances. A deterministic design approach may result in excessive sensitivity to minor variations, leading to suboptimal performance in real-world scenarios. Then, quantifying these uncertainties, and leveraging their influence on propeller performance, is of fundamental importance to design and optimizing configurations less sensitive to input variations. In the context of a "robust" design of marine propellers through simulation-based design optimization methodologies, this paper explores both deterministic and non- deterministic design approaches for a conventional propulsor, accounting for the uncertainties in the nominal operating conditions. Since the quantification of uncertainties can be computationally very intensive, an efficient medium-fidelity Boundary Element Method (BEM) solver using equivalent steady-state cavitating analyses is employed in the optimization process. The optimal designs are finally validated through fully unsteady and cavitating BEM and RANSE calculations to demonstrate the advantages of the non-deterministic design approach.