At the primal design stage of a new satellite, finite element model of the initial structure was established. Taking thicknesses of pipe beams and rectangle thin-wall beams as design variables, and considering constraints of natural frequency and strength, a structural optimization model was developed to approach minimum mass. Two-level multi-point approximation method was applied in structural optimization. In each calculation cycle, the original optimization problem was transformed to a first level multi-point approximate problem, and it was also approached by a second approximate problem which can be quickly solved by dual method. Three stages were implemented in the whole optimization process: initial optimum searching tests, design revision and re-optimization. Among the first stages, five runs were set with different constraints, design variables bounds and structural centroid heights, through which the design direction and interval of various structural parameters were obtained. Then the original structure was revised according to the results of the first stage. A new optimization model with fewer design variables and more reasonable variables bounds is established in the third stage and a feasible design is achieved, which provide references to detail design of the satellite structure. It indicates that the applied design procedure and optimization method are effective in engineering structural optimization problem.