It is suggested that many tropical coral reef fishes are living close to their upper thermal limits, with limited capacity to further acclimate to increasing sea surface temperatures (SSTs). Current maximum summer temperatures for the majority of coral reefs globally is 32°C, with an additional 3-4°C heating projected by 2100. However, the Persian/Arabian Gulf (PAG) is already experiencing summer maxima above 35°C, making it the hottest reef environment on earth, and creating a present-day example of end-of-century predictions. Here, we use PAG reefs as natural laboratories for climate change to investigate thermal acclimation and adaptation in three species of locally common coral reef fishes (Scolopsis ghanam, Cheilodipterus novemstriatus and Escenius pulcher). For each species we compared upper (CTmax) and lower (CTmin) thermal tolerance limits across populations from the environmentally extreme southern PAG, and populations from the more benign reefs in Gulf of Oman (GO) (annual temperature 22-32°C), focusing on five temperatures representing the existing seasonal PAG thermal range (18, 22, 27, 31.5, 35.5°C). Additionally, gill structure was assessed in S.ghanam to investigate thermally-induced remodeling of the cardio-respiratory system across 18°C, 27°C and 35.5°C. Fishes were collected throughout the year when SST matched that of experimental temperature, allowing an accurate representation of naturally occurring acclimation. As conditions in the GO do not reach the same seasonal extremes, fishes from this region were acclimated for >3 weeks to 18°C and 35.5°C before trials. Our results reveal significant differences between species, and between populations. There was a significant positive effect of treatment temperature on CTmax for all species, from both populations. All three species from PAG reached a higher CTmax at 35.5°C than GO fishes, as well as reaching a lower CTmin at 18°C. Minimal differences in CTmin were seen between populations, although species specific values varied significantly. There was considerable variation in CTmax between all species, and between populations, suggesting varying strategies in coping with increasing temperatures. C.novemstriatus was significantly less tolerant of both high and low temperatures at each treatment than S.ghanam and E.pulcher in both populations. Histological image analysis of S.ghanam gill structure across 18°C, 27°C and 35.5°C from PAG revealed a clear correlation between temperature and lamellar structure (n = 30). As temperature increased, lamellar length and perimeter significantly reduced, (ANOVA:  [F (2,58) = 38.937], p = < 0.01 and [F (2,58) = 11.874], p= <0.01, respectively), whereas lamellar density significantly increased (ANOVA [F (2,16) = 8.113, p = 0.004). S.ghanam from GO showed little difference in lamellar structure between temperatures. The presence of an interlamellar cell mass (ILCM) was detected in both populations at 18°C and 27°C, yet was not present at 35.5°C. The presence of ILCM represents a novel finding since it has previously not been documented in tropical reef fish species. Our results revealed that fishes from PAG displayed a greater thermal tolerance, suggesting that thermal adaptation has occurred. The ability to remodel various aspects of their gill structure, facilitating greater O2 uptake in higher temperatures, is likely a significant contributory factor. This study indicates that there may be capacity for some reef fish species to adapt to increasing SSTs.