The tectonic history of Eastern Indonesia has been a major interest since the successful hydrocarbon discoveries within the Mesozoic section in the Northwest Shelf of Australia, Timor Sea (Abadi Field), Bintuni, Berau and Seram. There have been numerous studies to understand the complex tectonic history and stratigraphy of the area. Sequence stratigraphic approach has proven to be the only effective method to unravel this vast area and this paper attempts to put previous studies and findings in perspective. Furthermore, this paper proposes a regional tectonostratigraphic chart to be utilized, hopefully, as a tool to work on underexplored Pre-Tertiary stratigraphic sections of Eastern Indonesia.The geology of Eastern Indonesia started with the separation of microcontinents from Gondwanaland in the Late Paleozoic, including fragments rifting and drifting from the Australian Continental Margin during the Mesozoic. Three major megasequences were identified and are related to the fragmentation of the Australian Continental Margin, which consist of Pre-rift, Syn-rift and Post-rift megasequences. The timing of each megasequence was different, especially between the southern area (Timor Sea, Abadi-Tanimbar and West Arafura area) and the northern area (Aru-Kumawa, Bintuni, Berau, Semai and Papua). The northern area was separated from the Australian mainland by Middle-Late Triassic, while the southern area separated from the Australian Continent by Late Jurassic. This implies that the syn-rift sediments in the north-eastern Indonesia are older (Late Permian-Triassic) than those to the south (Early Triassic-Late Jurassic). In other words, same-aged formation in the north is genetically different from the southern part of the area. As an example, the Jurassic reservoir sands at Bintuni Basin belong to a different megasequence than the Jurassic sands in the Timor Sea and Tanimbar area. The syn-rift reservoirs in Bintuni Basin remain underexplored.The new tectonostratigraphic chart and proposed paleo-depositional environment hopefully brings clarity and efficiency for hydrocarbon exploration in the area.