Ultra-high-altitude unmanned aerial vehicles have created a high demand for the performance of propellers under low Reynolds numbers, while the efficiency of such propellers by the existing design framework has reached a bottleneck. This paper explores the possibility of extending the Gurney flap on low Reynolds number propellers to achieve efficiency breakthrough. An iterative optimization strategy for propellers with Gurney flaps is established, in which cross-sectional airfoils can be continuously optimized under updated Reynolds numbers and lift coefficients. A computational fluid dynamics (CFD) simulation based on the γ-Re_θ model was used as an aerodynamic analysis method. Propellers with and without Gurney flaps were optimized successively. Optimal results were analyzed using the CFD method. Results showed that an optimal propeller with a Gurney flap can achieve an efficiency of 82.0% in cruising conditions, which is 1.8% higher than an optimal propeller without a Gurney flap. Compared with the latter, the consumed power of the optimal propeller with a Gurney flap can be reduced by 2.2% with the same advance speed. Furthermore, the variation of the improvement by the Gurney flap propeller, along with its Reynolds number, was studied. A wind tunnel test indicates that the performance of the propellers obtained by the CFD method are in good agreement with the test results.