Aggregates are the major constituents of concrete in terms of volume; therefore, they strongly affect concrete’s strength and durability. Coquina is one of the most abundant carbonate rocks found along the coastal area of the Persian Gulf, and due to its high porosity and low mechanical properties, is not generally used as concrete aggregate. This study aims to investigate the effect of limestone, travertine, and coquina aggregates on the physico-mechanical properties and durability of Portland concrete (PC) and sulfur concrete (SC). The durabilities of the formulated concretes were studied in different chemical solutions and different marine environments of the Persian Gulf. It was found that SC has higher strength and elastic modulus and lower effective porosity and water absorption compared to the PC made by the same type of aggregates. In PC, limestone and travertine gained a higher uniaxial compressive strength due to their lower porosity and higher physical properties than coquina. However, in SC, coquina, due to its high porosity, allowed SC to penetrate the pores and induce better adhesion. Therefore, coquina makes stronger SC than limestone and travertine. Laboratory aging test results show that SC has higher resistance against aging tests than PC made by the same aggregate types. Due to the higher strength and lower effective porosity and water absorption, the SC made by coquina was the most durable in artificial aging tests and different marine environments. Those SC placed in the tidal zone had the highest loss in strength and those placed in the submerged zone showed the lowest change in strength. Furthermore, due to the salt weathering, wetting-drying cycles, wave effects, and temperature differences in environments such as tidal zones, more care should be taken using SC. This study showed that it is possible to make concrete with acceptable physico-mechanical properties with weak aggregates such as coquina by changing the cement type.