Rhodolith beds are aggregations of free-living non-geniculate coralline red algae (Corallinales, Rhodophyta), with a high biodiversity of associated organisms. This is the first detailed study of a rhodolith-bed community from the cold-temperate waters of southern Australia. This bed, located at 1–4-m depth in Western Port, Victoria, is composed of four rhodolith-forming species (Hydrolithon rupestre (Foslie) Penrose, Lithothamnion superpositum Foslie, Mesophyllum engelhartii (Foslie) Adey and Neogoniolithon brassica-florida (Harvey) Setchell & Mason). M. engelhartii has a foliose growth form and the other three species have fruticose growth forms. Detailed descriptions are provided for all species, allowing reliable identification. Comparisons with other rhodolith beds and reported rhodolith-forming species, both in Australia and worldwide, are also provided. The invertebrate cryptofaunal community was quantified for two rhodolith-forming species. The density of cryptofauna inhabiting foliose and fruticose rhodolith growth forms did not differ significantly and neither did abundance of individual phyla. Mean density of fauna was 0.4 invertebrates cm^–3, the majority of which were polychaete worms. Comparisons of fauna associated with other rhodolith beds are also provided. A study of the vitality of the rhodolith bed showed dead rhodoliths are more abundant than live rhodoliths. Possible reasons for reduced bed vitality are explored.