Continuous recordings of 17 broadband and short period digital seismic stations from a newly established seismological network in Saudi Arabia, along with digital recordings from the broadband stations of the GSN, MEDNET, GEOFON, a temporary array in Saudi Arabia, and a temporary short period stations in Oman, were analyzed to study the lithospheric structure of the Arabian plate and surrounding regions. The Arabian plate is surrounded by a variety of types of plate boundaries: continental collision (Zagros belt and Bitlis suture), continental transform (Dead Sea fault system), young sea floor spreading (Red Sea and Gulf of Aden), and oceanic transform (Owen fracture zone). Also, there are many intraplate Cenozoic processes such as volcanic eruptions, faulting, and folding that are taking place. We used this massive waveform database of more than 6200 regional seismogram to map zones of blockage, inefficient, and efficient propagation of the Lg and Sn phases in the Middle East and East Africa. We observed Lg blockage across the Bitlis suture and Zagros fold and thrust belt, corresponding to the boundary between the Arabian and Eurasian plates. This is probably due to a major lateral change in the Lg crustal wave-guide. We also observed inefficient Lg propagation along the Oman mountains. Blockage and inefficient Sn propagation is observed along and for a considerable distance to the east of the Dead Sea fault system and in the northern portion of the Arabian plate (south of the Bitlis suture). These mapped zones of high Sn attenuation, moreover, closely coincide with extensive Neogene and Quaternary volcanic activity. We have also carefully mapped the boundaries of the Sn blockage within the Turkish and Iranian plateaus. Furthermore, we observed Sn blockage across the Owen fracture zone and across some segments of the Red Sea. These regions of high Sn attenuation most probably have anomalously hot and possibly thin lithospheric mantle (i.e., mantle lid). A surprising result is the efficient propagation of Sn across a segment of the Red Sea; an indication that active sea floor spreading is not continuous along the axis of the Red Sea. We also investigated the attenuation of Pn phase (QPn) for 1-2 Hz along the Red Sea, Dead Sea fault system, within the Arabian shield, and in the Arabian platform. Consistent with the Sn attenuation, we observed low QPn values of 22 and 15 along the western coast of the Arabian plate and along the Dead Sea fault system, respectively, for a frequency of 1.5 Hz. Higher QPn values on the order of 400 were observed within the Arabian shield and platform for the same frequency. Our results based on Sn and Pn observations along the western and northern portions of the Arabian plate imply the presence of a major anomalously hot and thinned lithosphere in these regions that may be caused by the extensive upper mantle anomaly that appears to span most of east Africa and western Arabia.