Rhodolith beds are major marine benthic macrophyte communities, comparable in size and significance to kelp beds, seagrass meadows and coralline reefs. Rhodolith beds are currently ‘at risk’, both around the world and in Australia, from anthropogenic disturbances such as ocean acidification, coastal degradation and sedimentation. However, knowledge of rhodolith distribution in Australia is limited and beds are currently largely considered to be uncommon and isolated. An extensive review was undertaken using herbarium collections, and relevant scientific and grey literature (journal publications, marine surveys, ships’ logs, reference books and websites) for references to rhodoliths and rhodolith beds. Our study has shown that rhodoliths are common throughout 70% of Australia’s coastline, ranging from tropical to cold-temperate waters, down to 117m, forming a vast natural resource in terms of area covered, biodiversity and carbonate production. This review has created a solid foundation for future rhodolith research in Australia by documenting the extent of known rhodolith distribution. It will help inform and influence future research and policy planning on these largely unexplored, highly diverse marine ecosystems.