The labyrinth spillway continues to be a popular type of the control structures. The focus of the present study is that on the optimization of the shape of the labyrinth spillway through the minimization of the construction costs because the use of it is a suitable solution in the rehabilitation process of existing reservoirs. An Adaptive Neural Fuzzy Inference System (ANFIS) model was developed to determine the discharge coefficient of the labyrinth spillway as a function of the angle between alignment of the crest and direction of flow, the relative depth of flow over spillway and its crest height. Differential Evolution (DE) algorithm and Genetic Algorithm (GA) were adopted to minimize the spillway cost as the objective function by considering certain hydraulic conditions as the constraints of the optimization procedure. The results indicated that DE and GA can respectively reduce 19.3% and 16.6% the. construction cost of a real benchmark design