Composite structures are usually subjected to fluctuating loads in service leading to fatigue failure. Because it is one of the main failure modes, fatigue behavior of composites has been extensively studied to be able to design fatigue-resistant composite structures. However, little attention has been paid to their design optimization under fatigue loading. In this study, a methodology is proposed to find the optimum fiber orientation angles of composite laminates under various in-plane loads to achieve maximum fatigue life. Fawaz-Ellyin's model is used to predict the fatigue life of the laminates. A variant of simulated annealing algorithm is used as the search algorithm in the optimization procedure. A number of problems are solved to demonstrate the effectiveness of the proposed method.