Phymatolithon (Corallinaceae, Rhodophyta) is represented in southern Australia by two species: P. repandum, previously recorded from the region, and P. masonianum sp. nov. Detailed morphological, anatomical and taxonomic accounts are provided along with comparisons to the type species of the genus, P. calcareum. A critical evaluation of the at least 16 characters previously used to delimit species within Phymatolithon has shown that only three are useful in delimiting southern Australian species, but five new features have also been found to have value in species delimitation. Four of the above eight relate to vegetative features and four to tetra/bisporangial conceptacle features. The latter can also serve to distinguish southern Australian species from the type species. Characters recently proposed to delimit Leptophytum from Phymatolithon have been found to be unsatisfactory, and Leptophytum is reaffirmed as a genus in need of further evaluation. Southern Australian species ascribed at some stage to Leptophytum have been found to belong to Phymatolithon. A short historical introduction is also provided along with keys to southern Australian species, information on distribution, seasonality and habitat, nomenclature and synonymy and concluding remarks.