Polychaete worm tubes within the mid to lower intertidal zone along the South African west coast were frequently observed to be overgrown by a minutely papillate species of encrusting coralline algae. Analysis of the vegetative and reproductive morphology and anatomy of this alga shows that it is new to science and belongs to the subfamily Melobesioideae and, in particular, to the genus Synarthrophyton, which is for the most part restricted to the Southern Hemisphere. Synarthrophyton papillatum is the tenth species from this genus and the sixth recorded from southern Africa. The new species is described in detail and compared with recently documented species found to conform to the generic description of Synarthrophyton. Synarthrophyton papillatum differs from S. patena and S. eckloniae in being epilithic, not epiphytic; from S. munimentum and S. robbenense in lacking raised rims on the tetrasporangial conceptacles; and from S. magellanicum in bearing minutely warty to fruticose protuberances and generally lacking the leafy to layered, weakly attached thalli present in the latter species. A key to the southern African species of Synarthrophyton is provided. Keywords: Corallinales, Hapalidiaceae, Non-geniculate coralline algae, South Africa, Synarthrophyton, S. papillatum, Taxonomy.