Utilization of seawater and undesalted sea sand in concrete production is expected to provide a sustainable way to solve the shortage of natural fresh water and river sand, and the durability of concrete structures is a progressively significant property due to the increasing demand for extended service life and less maintenance. In this study, the combined effects of wetting-drying cycles and sulfuric acid attacks on the properties of coated fly ash-based seawater and sea sand cementitious mortars were evaluated. Ordinary Portland cement mortar mixed with demineralized water and river sand (OPM) was manufactured as the reference group. Seawater and sea sand cementitious mortars with 0, 20, and 40 wt.% fly ash (FSSM1, FSSM2, and FSSM3) replacing cement were prepared for comparison. Xypex, a unique chemical treatment, was also adopted to coat the cementitious mortars to improve their durable performance. The performance of cementitious mortars with or without coatings exposure to 5 wt.% sulfuric acid solutions combined with the wetting-drying cycles for 1, 6, and 18 months was evaluated. The testing parameters include visual appearance, mass change, compressive strength, degradation depth, leaching behavior, and microstructural properties. The phase transformations of cementitious composites were studied with a multi-technique approach, including quantitative X-ray diffraction (XRD), Fourier transforms infrared spectroscopy (FTIR), thermogravimetric analysis (TGA), and backscatter electrons (BSE) with energy dispersive X-ray (EDX) and nuclear magnetic resonance (NMR). It is expected that the results of this study will contribute to the development of new construction materials that perform well in aggressive environments.