The present paper addresses the design and optimization of a flexible composite marine propeller. The aim is to tailor the laminate to control the deformed shape of the blade and consequently the developed thrust. The development of a hydro-elastic model is presented, and the laminate lay-up which minimizes the fuel consumption for the cruising and maximum speed conditions is simultaneously determined. Results show a reduction of 1.25% in fuel consumption for the combined case corresponding to a decrease of 4.7% in the cruising speed condition. Finally, the strength of the optimal blade is analyzed using the Tsai-Wu strength index. After local tailoring of the laminate configuration throughout the propeller a maximum value of 0.7 is determined indicating no failure will occur under normal operation conditions. The results suggest that it is possible to design a medium-sized flexible composite marine propeller that will enable a reduction of the fuel consumption while withstanding the imposed loads.