Tricleocarpa (Nemaliales) is a calcified, dichotomously branched red algal genus currently with two recognized species, T. cylindrica and T. fragilis, both widely distributed in warm temperate and tropical seas. We evaluated the relationships of Tricleocarpa using molecular markers, including 35 rbcL and 32 cox1 sequences, from specimens in the western Pacific, the Hawaiian Islands and South Africa. Our results demonstrated the presence of seven genetically distinct groups. The range of T. cylindrica was confirmed to include the West Indies, the Hawaiian Islands, and Asian waters, and specimens referable to T. fragilis were found in Asia. On the basis of our molecular analyses and detailed morphological examinations, we were able to discriminate two taxa that we here describe as new species: T. jejuensis sp. nov. and T. natalensis sp. nov. Tricleocarpa jejuensis, known from Korea, Japan, South Africa, and Taiwan, was distinguished by the presence of three to four cortical cell layers with elongated to compressed subsurface and innermost cells, monoecious sexuality, spherical cystocarps, and paraphyses intermixed with gonimoblast filaments. Tricleocarpa natalensis from Kwazulu-Natal, South Africa was characterized by three layers of elongate cortical cells, monoecious sexuality, hemispherical cystocarps, and paraphyses rarely intermixed with gonimoblast filaments. Our phylogenetic analyses indicated that three further clades were recognized at species level, but these were based on a few specimens and were not morphologically distinct; further sampling is needed in regions outside Asian waters before additional taxonomic revisions can be proposed.