Composite steel-concrete box girders are frequently used in bridge construction for their economic and structural advantages. An integrated metaheuristic based optimization procedure is proposed for discrete size optimization of straight multi-span steel box girders with the objective of minimizing the self-weight of girder. The metaheuristic algorithm of choice is the Cuckoo Search (CS) algorithm. The optimum design of a box girder is characterized by geometry, serviceability and ultimate limit states specified by the American Association of State Highway and Transportation Officials (AASHTO). Size optimization of a practical design example investigates the efficiency of this optimization approach and leads to around 15% of saving in material.