Despite differences in reef growth between the Arabian Gulf and the Red Sea, a common distinctive pattern of polygonal sills surrounding ponded depressions consistently occurs in shallow water. Viewed from a satellite, these seafloors are reticulated and maze like. Despite little current rainfall, this patterning is best explained by karst dissolution of limestone during periods of lower sea level. This is a paradox since such fine-scale karstification is confined to areas with considerably more precipitation than currently observed in Arabia. We resolve this apparent contradiction by developing a Pleistocene–Holocene chronology of sea level and climate for the Red Sea and Arabian Gulf, and through the use of pattern analysis and computer simulation, reveal the mechanism of formation for these structures. We demonstrate that this patterning can be taken as a Quaternary signature of paleohumidity in the now hyperarid Red Sea and Arabian Gulf.