Three independent line intercept transect surveys on northern Red Sea reef slopes conducted in 1988/9 and 1997/8 in Egypt and from 2006–9 in Saudi Arabia were used to compare community patterns and coral size. Coral communities showed scale-dependent variability, highest at fine spatial and taxonomic scale (species-specific within and among reef patterns). At coarser scale (generic pattern across regions), patterns were more uniform (regionally consistent generic dominance on differently exposed reef slopes and at different depths). Neither fine- nor coarse-scale patterns aligned along the sampled 1700 km latitudinal gradient. Thus, a latitudinal gradient that had been described earlier from comparable datasets, separating the Red Sea into three faunistic zones, was no longer apparent. This may indicate subtle changes in species distributions. Coral size, measured as corrected average intercept of corals in transects, had decreased from 1997 to 2009, after having remained constant from 1988 to 1997. Recruitment had remained stable (~12 juvenile corals per m2). Size distributions had not changed significantly but large corals had declined over 20 years. Thus, data from a wide range of sites taken over two decades support claims by others that climate change is indeed beginning to show clear effects on Red Sea reefs.