A number of molecular studies of the Corallinales, a calcified order of the red algae, have used the conservative nSSU gene to investigate relationships within the order. However interspecific variation at this locus is low for closely related species, limiting resolution of recently diverged groups. In this study, we obtained psbA sequence data from specimens of the order from New Zealand that had been identified according to current taxonomic criteria. We compared phylogenetic analyses based on psbA with those based on nSSU for the same dataset, and also analysed nSSU sequences of the New Zealand material with nSSU sequences of Corallinales taxa from other parts of the world. Our study shows that psbA has considerable potential as a marker for this group, being easily amplified and considerably more variable than nSSU. Combined analyses using both markers provide significant support for relationships at both distal and terminal nodes of the analysis. Our analysis supports the monophyly of all three families currently defined in Corallinales: the Sporolithaceae, Hapalidiaceae and Corallinaceae, and indicates cryptic speciation in Mesophyllum and Spongites.