This article presents evidence for over 4200 prehistoric shell midden sites distributed on opposite sides of the southern Red Sea. These sites were primarily discovered using survey methods and site location models developed for locating shell midden sites on the Farasan Islands, where over 3000 have been found during previous research. These sites have been extensively excavated in the field and dated. Combining predictive models with remote sensing, an additional 1200 sites have been detected on the opposite side of the Red Sea, centred on the Dahlak Islands in Eritrea. Before these discoveries on the Farasan and Dahlak Archipelagos, the number of published prehistoric shell midden sites in the southern Red Sea was less than twenty. Combined, these sites represent a significant addition to the prehistoric coastal archaeology of the region. These new shell midden sites, and their apparent similarities on the two opposing coastlines, may indicate evidence of cultural contacts across the Red Sea during the Holocene Red Sea.