The dimensioning of overhang slabs in bridge decks is usually based on simplified, thus conservative methods. The resulting over-dimensioned overhang bridge slabs can also affect the design of the girders. In this paper, an optimization procedure for the design of this structural element is presented. The aim is to minimize investment cost and global warming potential in the material production stage simultaneously while fulfilling all safety requirements. The design variables used in this study are the thicknesses of the overhang slab and the height of the edge beam. However, a complete detailed design of reinforcement is performed as well. Both a single-objective and a multi-objective formulation of the nonlinear problem are presented and handled with two well-known optimization algorithms: pattern search and genetic algorithm. The procedure is applied to a case study, which is a bridge in Sweden designed in 2013. One single solution minimizing both objective functions is found and leads to savings in investment cost and CO2-equivalent emissions of 4.2% and 9.3%, respectively. The optimization procedure is then applied to slab free lengths between 1 and 3 m. The outcome is a graph showing the optimal slab thicknesses for each slab length to be used by designers in the early design stage.