As demand for sustainable construction materials grows, this study investigates fly ash (FA) as a partial replacement for composite Portland cement (PCC) in concrete. The effects of FA incorporation on flexural strength and environmental performance were evaluated using mixtures containing 0%, 15%, 30%, and 45% FA by weight of PCC. Flexural strength was measured at 28 and 90 days, while environmental performance was assessed through Life Cycle Assessment (LCA) using six impact categories: abiotic depletion potential (ADP), acidification potential (AP), eutrophication potential (EP), global warming potential (GWP), ozone depletion potential (ODP), and photochemical ozone creation potential (POCP). An acceptance criterion based on flexural strength was established to assess the feasibility of FA substitution. Although increasing FA content reduced flexural strength compared with the reference concrete, all FA mixtures retained more than 75% of the reference strength, satisfying the acceptance criterion and confirming their suitability as partial PCC replacements. Environmentally, FA incorporation increased ADP but consistently reduced AP, EP, GWP, ODP, and POCP, indicating a trade-off between greater abiotic resource use and lower impacts in other categories. Integrated multi-criteria analysis identified the M-45FA mixture as having the highest overall eco-structural efficiency, highlighting FA’s strong potential as a sustainable supplementary cementitious material.