This study analyzes the stratigraphic evolution of the SW margin of the Sandakan basin with respect to implications for petroleum exploration. Integrated sequence stratigraphic tools and seismic stratigraphy was used to construct a stratigraphic models based on seismic facies pattern related to well data. This enables defining play concepts related to prospective petroleum accumulations. Furthermore, the study establishes the relationship of the structures to the formation of traps and reservoirs. Analysis of the seismic and wireline data shows that the basin is covered by marine-dominated deltaic sequences. The structures mapped reveal that the sequences have undergone periods of growth faulting, slumping and shale diapirism. A comparison of the interpreted sea-level curve and the eustatic Haq et al. (1987) curve shows major mismatches. This indicates that factors such as diapirism, tectonism, changing sediment supply and subsidence rates have affected the relative se-level. Late Miocene sands associated with slumps and possible turbidites deposited in the prodelta environment during lowstand can be considered as good reservoir.