Analysis of 2D seismic data over 4 500 km in length from the Madura Strait Basin in the East Java Sea reveals seismic reflection characteristics of reefs and associated sedimentary bodies, including asymmetrical or symmetrical dome reflections, slope progradational reflections, chaotic reflections and discontinuous strong reflections inside the reef, which onlap the flank of the reef. It is concluded that the developmental paleo-environment of most reefs is mainly conducive to shallow marine carbonate platform facies and platform margin facies, based on well core data, variations in seismic facies and strata thickness. The formation and evolution of all reefs are primarily influenced by the tectonic framework of the Madura Strait Basin. Platform margin reefs are principally controlled by two types of structures: one is a series of E-W trending Paleogene normal faults, and the other is an E-W trending Neogene inversion structures. In addition, wave actions, tidal currents and other ocean currents play an accelerated role in sorting, rounding and redeposition for the accumulation and evolution of reefs. Tertiary reefs in the MSB can be divided into four types: 1) an open platform coral reef of Late Oligocene to Early Miocene, 2) a platform margin coral reef controlled by normal faults in Late Oligocene to Early Miocene, 3) a platform margin Globigerina moundreef controlled by a “hidden” inversion structure in Early Pliocene, and 4) a platform margin Globigerina mound-reef controlled by thrust faults in the early Pliocene. Patterns of the formation and evolution of reefs are also suggested.