The Red Sea is identified as a new hotspot for large-scale atmospheric gravity waves (AGWs). SAR imagery reveals their 2D structure, while favorable propagation conditions are investigated on a seasonal basis. Using weakly nonlinear long wave theory and the observed characteristic wavelengths we obtain phase speeds which are consistent with those observed and typical for AGWs, with the Korteweg-de Vries theory performing slightly better than Benjamin-Davis-Acrivos-Ono. Satellite data between 1993 and 2008 reveals sea surface signatures consistent with horizontally propagating large-scale internal waves, which cover the entire Red Sea and are more frequently observed between April and September (although they also occur during the rest of the year). Possible generations mechanisms are briefly discussed.