Reducing the weight and increasing the torsion stiffness are the two main pursuits in propeller blade structure design. And the application of composite materials has improved the designability of propeller structure. In this paper we present an optimization process on a composite propeller blade, in which the composite layup numbers and angles are optimization parameters, the strength and bending stiffness are optimization constraints and the weight and torsion stiffness are optimization objectives. Non-dominated Sorting Genetic Algorithm is adopted to get a Pareto front of the two objectives. Results show that the optimization method is effective.