This paper reports the discovery of extensive middle Eocene bryozoan reef complexes along the paleoshelf edge of the Great Australian Bight (GAB). The complexes form the earliest carbonate deposit in the GAB, which is the largest Cenozoic cool-water carbonate province on Earth. The bryozoan reef mounds, previously misidentified as volcanic bodies, were deposited parallel to the shelf margin for more than 500 km along strike. Individual reef mound complexes are 60–150 km long, as wide as 15 km, and as thick as 200 m, and dwarf all previously described examples. Superimposed on the distal margin of an underlying Paleocene to mid-Eocene siliciclastic delta complex, the reef mounds provide a critical insight into changing paleoenvironments of the Australo-Antarctic Gulf ca. 43 Ma, coinciding with global and continent-wide climatic and tectonic events. The rapid growth and demise of reef mound–building bryozoans raises new questions regarding the interplay of Southern Ocean opening, ocean currents, and biosphere interactions.