The optimization methodology of the steel-concrete composite beam was proposed in this paper. The objective function is the cost of the composite beams, and the design variables are the geometry parameters, including height and width of the concrete deck, as well as thickness of the steel flange and web. The constraint conditions are main requirements stated in Chinese code for the design of composite beam, reasonable calculating theories and indispensable constructions, as well as some mature and consistent conclusions confirmed by experimental studies. Stiffness reduction coefficient is used to consider the effect of bond-slip effect between concrete and steel when calculating the beam deformation. The optimization for composite beam under uniform loads is given as a demonstration example finally. The methodology proposed in this paper should be useful for obtaining the solution of this kind of optimization problem.