Fly ash is a sustainable partial replacement of Portland cement that offers significant advantages in terms of fresh and hardened properties of concrete. This paper presents the findings of a study that aims at assessing the durability and strength properties of sustainable self-consolidating concrete (SCC) mixes in which Portland cement was partially replaced with 10%, 20%, 30%, and 40% fly ash. The study confirms that replacing Portland cement with fly ash at all of the percentages studied improves resistance of concrete to chloride penetration. The 40% fly ash mix exhibited the highest resistance to chloride penetration compared to the control mix. Despite the relative drop in compressive strength after 7 days of curing, the 28-day compressive strength of 40% SCC mix reached 55.75 MP, which is very close to the control mix. The study also confirms that adding 1%, 1.5%, and 2% basalt fibers, respectively, to the 40% fly ash mix improves the resistance to chloride penetration compared to the mix without basalt fibers.