Corals in the Persian/Arabian Gulf (PAG) are resilient to various stressors, whose levels exceed those of coral reefs globally. These corals thereby offer insight into mechanisms underlying thermal resilience, e.g., regarding the role of endosymbiotic microalgae in the family Symbiodiniaceae. Previous studies have identified the thermotolerant species Cladocopium thermophilum as broadly associated with corals in the southern PAG. However, algal-host specificity at the within-species level and the temporal stability of these associations are not well understood. Here we sampled two dominant stony corals (Porites harrisoni, n = 119 and Platygyra daedalea, n = 79) at three sites in the southern PAG and the neighboring Gulf of Oman (GO) to explore algal symbiont assemblage and specificity, whereby a prior dataset provided the opportunity to assess symbiont community stability in P. daedalea across a decadal time frame. Using high-throughput ITS2 marker gene sequencing and the SymPortal framework, we identified distinct, largely non-overlapping ITS2 type profiles of C. thermophilum as the dominant symbiotic partners in P. harrisoni and P. daedalea in the southern PAG, highlighting high host fidelity at the subspecies level. Despite this, we observed notable changes in C. thermophilum genotype diversity and an overall decrease over the course of a decade. By comparison, algal symbiont diversity in the neighboring GO corals increased, with formerly prevalent ITS2 type profiles being replaced by novel genotypes. Decadal data on P. daedalea suggest a shift in algal symbiont assemblage signified by the decline of formerly dominant algal type profiles and the emergence of novel genotypes. It is currently unknown whether the respective coral colonies associated with novel algae or became rare or extinct themselves. Understanding long-term algal population dynamics is critical to forecast how algal lineage loss or, alternatively, an increase in algal diversity will impact coral resilience and survival.