This paper presents the result of an investigation on the performance of concrete produced with different coarse aggregate sizes (CAS) and fully immersed in 5% sodium sulfate solution. Concrete mixtures were prepared with two water-to-binder ratios of 0.35 and 0.45 using four different maximum particle sizes (Dmax) of coarse aggregates (9.5 mm, 12.5 mm, 19 mm, and 25 mm). Test results indicate that the workability of concrete increases with increasing the CAS. Concrete made with Dmax of 12.5 mm shows the highest compressive strength, whereas concrete made with Dmax of 25 mm shows the lowest compressive strength. In addition, the compressive strength of concrete immersed in sulfate solution reduces around 8–13% in comparison with that of concrete cured in water. Moreover, all of the concrete samples perform good durability with ultrasonic pulse velocity values of all greater than 4200 m/s.