Multivariate analysis revealed distinct sub-regional coral communities among the southern Persian Gulf, Strait of Hormuz, and Gulf of Oman. Differences in community structure among locations were associated with considerable spatial heterogeneity in oceanic conditions, and strong directional environmental gradients. Despite clear community differences, considerable changes to coral community structure have occurred throughout the northeastern Arabian Peninsula as compared with previous studies. The most dramatic of these are the apparent changes from Acropora dominated to poritid and faviid dominated communities, particularly in the southern Persian Gulf and Strait of Hormuz. Although temperature and salinity have previously been cited as the major environmental factors structuring coral communities around the region, additional environmental parameters, including chlorophyll-a, surface currents and winds are shown to be important in structuring reef communities throughout the northeastern Arabian Peninsula.