The peculiar environment of Sharm El-Sheikh area, upon which its tourism industry is based, is undoubtedly threatened by different sources of pollution that are directly related to the rapid growth of the city, the influx of millions of tourists every year, and to the increased maritime activities in the Gulf of Aqaba and the Red Sea. The 1999's oil spillage in Sharm El-Maya Bay represented an extreme example of one of these threats. Although the spillage itself was promptly contained, only few studies were conducted to investigate the source of the pollution and its spatial and temporal variations. The present study, therefore, aimed to determine the extent of the pollution, its spatial variation, and its source. Three different types of samples were collected and analyzed for petroleum hydrocarbons. They included sediment samples from the headland, and samples of seabed sediments and seawater from the subtidal zone. Total hydrocarbons were determined using conventional gravimetric techniques. The results showed that the average concentration of the total hydrocarbons was 661.7±383.16 μg/g in the headland, 170±128.59 μg/g in the seabed, and 37.99±17.45 mg/L in the seawater. The results also indicated that the average content of total hydrocarbons in seawater samples was considerably higher than that estimated earlier. Spatial and temporal variations in the total hydrocarbon contents are suggestive of a land-based source of pollution related to damaged-underground fuel-storage tanks and pipelines that are actively polluting the bay.