This paper deals with a stage optimization problem of multi-stage missile. The missile covered in the study is three-stage missile, of which the first and second stages have propulsion system and the third stage is a kill vehicle to intercept a target. An evolutionary based optimization algorithm is used to optimize the propulsion stage weights of the missile. To deal with a trajectory optimization problem simultaneously, linear tangent law and proportional navigation guidance law are implemented to the optimization algorithm. Subsystem parameters, such as thrust, specific impulse, body diameter, and aerodynamic coefficients are considered as design requirements, so they are given in advance. The goal of the problem is to minimize the total system weight for cost savings. In order to verify the result from the evolutionary algorithm, optimization results via a pseudo-spectral method are compared. At the same time, the limit of gradient-based search method is discussed.