Spillways are essential parts of dams, in which the main task of these structures is to allow the passing of excess water and floods from the upstream to the downstream. In this regards, the main goal of this paper is proposing a novel framework for the probabilistic design of labyrinth spillway structures using a new developed reliability-based design optimization (RBDO) approach. In this RBDO approach, the total volume of the spillway is considered as the objective function of the optimization problem under uncertainties, while the labyrinth spillway parameters are considered as the design variables. Hereafter, to solve the formulated RBDO problem of the labyrinth spillway design, a new proposed model that consist of coupling the Monte Carlo Simulation (MCS) with a hybrid Artificial Neural Network (ANN) based Whale Optimization Algorithm (WOA) model is developed. The hybrid ANN-WOA is utilized to approximate the labyrinth spillway response in order to reduce the computational cost during the RBDO analysis. The proposed MCS-ANN-WOA model was implemented on the Ute dam labyrinth spillway at Logan, New Mexico (USA). The obtained results showed that the proposed RBDO model performance is more accurate and robust compared to the deterministic optimization (DO) approaches for an optimal design of the labyrinth spillway shape with the consideration of the safety levels.