The present research introduces a model to find the best shape of a dam's spillway under climate change impacts, considering a benchmark problem (i.e., Ute Dam's labyrinth spillway in the Canadian River watershed, New Mexico, USA). A spillway design is based not only on historical data but also on the future hydrologic events. Climate variables were predicted for the years 2021–2050 based on three representative concentration pathway (RCP2.6, RCP4.5, and RCP8.5) scenarios of the general circulation model from the fifth phase of the coupled model intercomparison project (CMIP5) using the statistical downscaling model. Streamflow at the USGS 07226500 streamgage was simulated by a rainfall–runoff model with predicted data. Instantaneous peak flow was estimated using an empirical method. Flood frequency analysis was used for the estimation of the design flood. The shuffled frog-leaping algorithm (SFLA) is used to optimize a labyrinth spillway design and its results were compared with two other nature-inspired algorithms: invasive weed optimization (IWO) and cuckoo search (CS). The spillway was optimized once with the actual design flood (16,143 m3/s) and again with the design flood under climate change (12,250 m3/s). Results revealed that optimization with realistic design flood reduced the concrete volume of the spillway by 37% and under climate change by 43% using the SFLA.