Ice formation on a wind turbine alters the airfoil profiles of the blades and causes degradation in the aerodynamic performance of the wind turbine and the resulting power production losses. Since the blade profile plays a significant role in the icing of a blade, power production losses due to icing can be minimized by optimizing the blade profile against icing. In this study, blade profiles are optimized in order to minimize power production losses. A Gradient based aerodynamic shape optimization method is developed together with the Blade Element Momentum method and an ice accretion prediction tool in order to minimize the power production losses of horizontal axis wind turbines under various icing conditions. In an optimization study performed for the AeolosH 30 kW and NREL 5 MW wind turbines exposed to icing conditions up to 1 h, the power loss due to icing is reduced by about 4%.