Ground granulated blast furnace slag (GGBFS) and sulfate were used to reinforce and modify circulating fluidized bed fly ash (CFBFA)-based cementitious materials. The cement content in cementitious material was 30% (mass fraction, the same below), the total content of CFBFA and GGBFS was 70%, and the addition of desulfurization gypsum and sodium sulfate was 0%~4% and 0%~1.5%, respectively. The effects of the mass ratio of CFBFA and GGBFS and the content of desulfurization gypsum and sodium sulfate on the setting time and mortar compressive strength of the composite cementitious materials were studied. Then the composite reinforcement mechanism of GGBFS and sulfate on CFBFA-based cementitious materials was investigated by X-ray diffraction (XRD) and scanning electron microscopy (SEM). The results show that CFBFA-based cementitious materials have long setting time and low compressive strength. The composite of CFBFA and GGBFS can significantly improve the 3 and 7 d compressive strength of cementitious materials, but the reinforcement strength of 28 d is limited. The introduction of sulfate in CFBFA-GGBFS system can significantly improve the compressive strength. Desulfurization gypsum whose suitable content is 2% is more effective in improving the strength of low content CFBFA system, and sodium sulfate whose suitable content is 0.5% have a better effect on the strength reinforcement of high content CFBFA system, but sodium sulfate has a negative effect on the 28 d compressive strength. The composite of CFBFA and GGBFS increases the amount of gel generation in the early hydration stage of cementitious materials. Desulfurization gypsum can accelerate the formation rate of ettringite (AFt) and stabilize its growth. Sodium sulfate reacts with Ca(OH)2 to form strong alkaline NaOH and highly active CaSO4, which further increases the formation rate of gel and AFt.