Thirty-five subsurface samples from Dib-1 and Gs. 392/2 wells Gulf of Suez and twenty-two samples from surface section at the Midyan region east Gulf of Aqaba, are palynologically analyzed. All studied samples are colected from the Nukhul Formation of Suez Gulf and from the Sharik and Musayr Formations in the Midyan region. Palynological study of these samples confirmed the early Miocene age for these formations. The palynoflora was not diverse enough to allow biostratigraphic applications. Ttwenty-two families and seventeen genera can be identified. The recorded pollen grains indicated a transitional floristic change from warm to humid temperate that characterized the Early Miocene deposits.