In recent decades, global climate change has caused profound biological changes across the planet. However, there is a great disparity in the strength of evidence among different ecosystems and between hemispheres: changes on land have been well documented through long-term studies, but similar direct evidence for impacts of warming is virtually absent from the oceans, where only a few studies on individual species of intertidal invertebrates, plankton, and commercially important fish in the North Atlantic and North Pacific exist. This disparity of evidence is precarious for biological conservation because of the critical role of the marine realm in regulating the Earth's environmental and ecological functions, and the associated socioeconomic well-being of humans. We interrogated a database of >20,000 herbarium records of macroalgae collected in Australia since the 1940s and documented changes in communities and geographical distribution limits in both the Indian and Pacific Oceans, consistent with rapid warming over the past five decades. We show that continued warming might drive potentially hundreds of species toward and beyond the edge of the Australian continent where sustained retreat is impossible. The potential for global extinctions is profound considering the many endemic seaweeds and seaweed-dependent marine organisms in temperate Australia.