For stiffness design optimization of composite frame structures, one of the major problems when using fiber winding angles as design variables directly is the lack of convexity of the objective function, which may lead to different local optima depending on initial designs when a traditional gradient-based optimization algorithm is applied. Therefore, the present paper adopts a gradient-based two-step optimization scheme to cope with the difficulty and search for a better optimal design of composite frames in which the fiber winding angles are taken as design variables. To realize the two-step optimization scheme, the equivalent stiffness parameters of a composite beam with circular cross-section are derived in explicit expressions and used to force the convexity of the design optimization of the composite frame. The stiffness matrices are linearly expressed in terms of the stiffness parameters, which guarantee the convexity of the design variable feasible region in the stiffness parameter space. The equivalent stiffness parameters are adopted to keep invariance of physical quantities between fiber winding angle and equivalent stiffness parameter spaces. In the two-step optimization scheme, the minimum identification problem with the constraint that the objective function at the new starting point is less than or equal to the previous objective function at the optimum point in fiber winding angle space is established. Then, the two-step optimization scheme can be implemented in the fiber winding angle and structural equivalent stiffness parameter spaces, respectively, until the minimum identification problem is not possible to identify a new starting point. The proposed two-step optimization scheme for composite frames fully takes advantage of the stiffness parameters in convexity and fiber winding angles as practically physical quantities, respectively. The sensitivity information of the objective function with respect to fiber winding angles and equivalent stiffness parameters is derived by the analytical sensitivity analysis method. Numerical examples show that the two-step optimization scheme can effectively force convexity of the optimization model and help to eliminate the initial design dependency. The effectiveness of the proposed two-step scheme is further verified through the particle swarm optimization (PSO) algorithm which is an evolutionary algorithm with global optimization capability.