Partially replacing cement with supplementary cementitious materials (SCMs) has been extensively studied in the past. Despite the ability of SCMs to alleviate the environmental concerns of cement, the mechanical properties of cement mortars incorporating SCMs are affected by such modifications to mix design. Flexural strength is essential for cement mortar applications, such as repair and retrofitting. In this study, the Taguchi method was used to optimize the mixture proportions of cement mortar incorporating natural pozzolan (NP) as an SCM for superior flexural strength. The factors and their corresponding levels considered in this investigation included the binder content at 350, 400, 450, and 500 kg/m3, water-to-binder (w/b) ratio at 0.450, 0.475, 0.500, and 0.525, dune sand percentage replacement of natural sand at 5, 10, 15, and 20%, NP percentage replacement of cement at 5, 10, 20, and 40%, and high range water reducer (HRWR) dosage at 0.25, 0.50, 0.75, and 1.00%. The response criterion was the 28-day flexural strength. Sixteen mixes were cast, cured for 28 days in water, and tested for flexural strength. The optimum mortar mix had a binder content of 500 kg/m3, a water-to-binder ratio of 0.500, a dune sand content of 20%, a natural pozzolan content of 40%, and high range water reducer of 1% by binder mass. Its 28-day flexural strength response was 7.2 MPa. The study highlights the possibility of creating cement mortar mixes having high flexural strength for construction applications while substituting 40% of the cement with NP.