In this paper, the corrosion of C-steel in OPC-fly ash-composite cement pastes (OPC-FA-CCP) was examined with different fly ash (FA) contents (0, 10, 25 and 50 mass%) and immersion times in the absence and presence of spinach extract as a green-corrosion inhibitor. The effect of replacing FA in cement composition on its physical, chemical, mechanical and microstructure properties using a variety of techniques has been also studied. The results indicated a significant increase in compression strength (CS) and gel/space ratio (X) upto 90 days in the case of OPC-FA-CCP containing 10 mass% FA. At higher FA replacement levels (25–50 mass%), the CS and X values decreased. SEM confirmed the presence of a surface layer of amorphous-ill-crystalline C-S-H as a gel product on the FA grains, with prolonged time showing dense crystalline hydrated fibril-C-S-H products. The C-steel immersed in the pure OPC cement (FA0S) has the highest corrosion potential (Ecorr = −461 mV) vs. SCE. With the increase of the FA content the Ecorr shifts to a more negative value with an indication of the decrease in the corrosion resistance of the rebar. During the first 6 h of immersion, the increased thickness of the passive film leads to a remarkable decrease in the corrosion rate. As the dipping time increases, the current corrosion density in all tested OPC-FA-CCP mixtures is unexpectedly reduced. A significant improvement in corrosion resistance of rebar was achieved in the presence of spinach extract. All the corrosion parameters were also calculated.