Current study proposes an effective way to modify the properties of super-sulfated cement (SSC) paste and mortar with preheated flue gas desulfurization (FDG) gypsum at different temperatures and durations, and different sulfate compositions. Preheated FGDs with temperatures between 25 and 150 °C and durations between 0 and 24 h were used to replace 5, 10 and 15 mass/% of slag in SSC. Besides the ordinary Portland cement, the sodium hydroxide (NaOH) was also used as the alkali activator. Both anhydrite and sodium sulfate with five different contents were used to provide the ions of SO3 to react with the ions of Ca and Al released from slag during hydration to form ettringite. Experimental results showed that partial replacement of untreated FDG with either the specifically preheated FDG or the commercial sulfates noticeably enhanced the early hydration of modified SSC pastes with setting time being significantly shortened and increased the compressive strength, while the NaOH solution delayed the setting time and reduced the compressive strength. Microstructural examinations revealed that using partial preheated FDG or commercial anhydrite did not alter the hydrated components, but significantly enhanced the fractions and stabilized the crystallization of those hydrates with hydration time.