Structural optimization algorithm of steel box girder bridges using improved higher-order approximate reanalysis technique is proposed in this paper. The proposed approximation method is a generalization of the convex approximation method. The order of the approximate reanalysis for each function is analytically adjusted in the optimization process. This self-adjusted capability makes the approximate structural analysis values conservative enough to maintain the optimum design point of the approximate problem. The efficiency of proposed optimazation algorithm, compared with conventional algorithm, is successfully demonstrated in the steel box girder bridges. The efficiency and robustness of proposed algorithm is also demonstrated in practical steel box girder bridges.